CS 154
Formal Languages and Computability
1730-1845 TTh, MH 224
Jeff Smith, MH 415, 924-5153
smithj@mathcs.sjsu.edu
Office hours:
1730-1900 MW, 1600-1730 Tu,
1700-1730 TTh, or by appointment.
Text:
Linz, An Introduction to Formal Languages and
Automata.
Other helpful texts are those by Martin, Lewis & Papadimitriou,
Hopcroft & Ullman, and Cohen. These, and perhaps other references,
will be in the reserve book room.
Grading system:
20% on problem sets
60% on 4 1-hour exams
20% on final exam
All exams will be open book and open notes.
The final grade will be computed by adding your scores and
comparing to the sum of the grade brackets for all the assignments
and tests. In borderline cases, consideration will be given to
those who did the homework regularly or improved during the
course.
Topics:
Finite automata, context-free grammars, Turing machines and
computability. This corresponds roughly to the material in Chapters
2-12. We will also cover Section 1.2; you should already know the
material in Section 1.1.
Collaboration:
The work you turn in should be your own.
Please become familiar with the official university policy on
academic dishonesty on pp. 446-47 of the 1995-97 catalog.