| cs386 website: |
http://www.calstatela.edu/faculty/vcrespi/CS/CS386/cs386.html |
| Lectures: |
TR 4:20-6:00pm, ET A210
|
| Final Exam: |
Tuesday, Dec 6, 4:30-7:00pm, ET A210
|
| Instructor: |
Valentino Crespi
vcrespi@calstatela.edu
(323) 343-4596.
ET-A318
|
| Office Hours: |
MW 3:00-4:00pm, TR 6:00-7:00pm.
|
| 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: |
MATH255, CS202 |
| Textbook: | J. Hopcroft, R. Motwani,
J. Ullman. Introduction Automata Theory, Languages and
Computation. Addison-Wesley. |
| References: |
- Arto Salomaa. Computation and Automata. Cambridge
University Press.
- Peter Linz. An Introduction to Formal Languages and Automata
(3rd edition). Jones and Burtless Publishers, 2001.
|
| 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.
- 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.
|
| 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 will not be tolerated. Cheating on any assignment or exam
will be taken seriously. All parties involved will receive a grade
of F for the course and be reported to the Academic Senate. |
| General 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.
- 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.
|