| cs386 website: |
http://www.calstatela.edu/faculty/vcrespi/CS/CS386/cs386.html |
| Lectures: |
ET-A210, TR 1:30-3:10pm
|
| Final Exam: |
Tuesday, December 2, 2008. Time: 1:30-4:00pm
|
| Instructor: |
Valentino Crespi
vcrespi@calstatela.edu
(323) 343-4596.
ET-A318
|
| Office Hours: |
M 4:00-6:00pm, TR 3:30-4:30pm
|
| Course Description: |
Formal approach to automata theory; finite state machines,
regular expressions, regular languages. Develops mathematical
foundation for Computer Science. |
| Course Goals: |
At the end of the course, students are able to
- Understand and manipulate formal descriptions of languages,
automata and grammars with focus on Regular and Context Free
Languages, Finite State Automata and Regular Expressions.
- Apply rigorously formal mathematical methods to prove properties
of languages, grammars and automata.
|
| Prerequisites: |
MATH248, CS202 |
| Textbook: | Peter Linz. An
Introduction to Formal Languages and Automata (4th
edition). Jones and Burtlett Publishers, 2006.
|
| References: |
- Arto Salomaa. Computation and Automata. Cambridge
University Press.
- J. Hopcroft, R. Motwani, J. Ullman. Introduction to Automata
Theory, Languages and Computation. Addison-Wesley.
|
| Topics: | This is a general
overview. However you can access the archive to see full logs of
previous instances of this same course.
- Mathematical Preliminaries and Proof Techniques: sets,
alphabets, strings, languages, proofs by contradiction and
structural induction.
- Grammars and Automata: language generation and language
recognition.
- DFA and NFA. The Subset construction.
- Regular Languages and Regular Expressions.
- Minimization of DFA.
- Linear Grammars.
- Pumping Lemma for Regular Languages.
- Context Free Languages.
- Parse Trees. Leftmost and rightmost derivations. Ambiguity.
- PDA and DPDA.
- Pumping Lemma for Context Free Languages.
|
| Grading Policy: |
Two Midterm Exams (25%+25%), Final Exam (40%), Homework Assignments (10%)
| Score (%) |
Letter Grade |
|
90-100
|
A
|
|
80-89
|
B
|
|
60-79
|
C
|
|
50-59
|
D
|
|
0-49
|
F
|
|
| Academic Integrity: | Students are
allowed and encouraged to discuss reading materials with each
other. However, homework assignments must be solved and written
individually. If you obtain a solution with help then you
should acknowledge your source in the paper and then write
independently your own solution.
Cheating on any exams will not be tolerated. |
| General Policies:
|
- Makeup Exams: No.
- Use of Cell Phones: forbidden.
- Office:
Students are warmly invited to visit the instructor (during
the announced office hours) for questions and clarifications.
- E-mail:
E-mails addressed to vcrespi@calstatela.edu must have, in the
subject, the keyword CS386 (e.g. Subject: CS386 ...).
All the E-mails will be possibly processed in the evening and so
will be answered with a minimum delay. Be careful, the keyword in
the subject is important for automatic filtering. Wrong subjects may
result in the accidental loss of the message.
|