| Instructor: |
Valentino Crespi, ET-A318, 3-4596.
vcrespi@calstatela.edu
Office Hours: MW 1:00-2:00pm, T 12:30-2:30pm.
|
| cs386 website: |
http://www.calstatela.edu/faculty/vcrespi/CS/CS386/cs386.html |
| Prerequisites: |
MATH255, CS202 |
| Schedule: |
MW 6:10-7:50PM ET-A210 |
| Abstract: |
CS386 focuses on regular languages, Context Free Languages
(CFLs), Finite State Automata (FSA) and Pushdown Automata (PDA).
The main purpose of the course is to help students familiarize with
basic formal methods that apply heavily in the theory of languages
and in particular in the design of syntax and lexical
analyzers. |
| Topics Overview: | 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.
- DFSA and NDFSA. The Subset construction.
- Regular Languages and Regular Expressions.
- Minimization of DFSA.
- 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.
|
| Course Book: | J. Hopcroft, R. Motwani,
J. Ullman. Introduction Automata Theory, Languages and
Computation. Addison-Wesley. |
| Grading: |
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
|
|
| Date and Time of Final Exam: |
Monday, June 6, 2005. Time: 7:30-10:00pm. |
| Policies:
|
- Makeup Exams: No.
- Homework Assignments:
Homework assignments should be written neatly on standard sized
paper (8.5 x 11 inch), possibly in black or blue ink (please do not
use red) and submitted at the due date (no electronic
submissions accepted). Each page should be numbered. Late
submissions will not be accepted.
- Use of Cell Phones: forbidden.
- Late arrivals:
Students arriving 30min after the beginning of class will not be
admitted.
- Academic integrity and honesty:
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.
- 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.
|