| Instructor: |
Valentino Crespi, ET-A221, 3-4596.
vcrespi@acm.org
Office Hours: M 12:30-2:30pm, W 12:30-1:30pm, R 5:00-6:10pm
|
| cs386 website: |
http://www.calstatela.edu/faculty/vcrespi/CS/CS386/cs386.html |
| Prerequisites: |
MATH255, CS202 |
| Schedule: |
MW 10:50-12:30PM ET-A332 |
| Abstract: |
CS386 focuses on regular languages and Finite State Automata.
The main purpose 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 (cp. 1-5): |
- Mathematical Preliminaries and Proof Techniques: sets,
strings, languages and structural induction.
- DFSA and NDFSA.
- Regular Languages and Regular Expressions.
- Pumping Lemma.
- Grammars and Automata: language generation and language recognition.
- Regular Grammars.
- PDA.
- Context Free Languages.
|
| Course Book: |
Peter Linz. An Introduction to Formal Languages and Automata
(3rd edition).
Jones and Burtless Publishers, 2001. |
| Recommended 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, December 8, 2003. Time: 10:45-1:15pm. |
| 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.
- 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 Valentino.Crespi@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.
|