Lectures: MW 2:30 - 3:45, 001 Stanger
Text: An Introduction to Formal Languages and Automata 3rd edition, by Peter Linz, Jones and Bartlett Publishers, 2002
Description: A theoretical treatment of what can be
computed
and how fast it can be done. Applications to compilers, string
searching,
and control circuit design will be discussed. The hierarchy of finite
state
machines, pushdown machines, context free grammars and Turing machines
will be analyzed, along with their variations. The notions of
decidability,
complexity theory and a complete discussion of NP-Complete problems
round
out the course.
Exams: There will be one midterm (25%) and one final examination (35%), dates TBA.
Assignments: Homeworks will be worth 40% of your grade. You should do these with a partner, and one grade will be given to both people in each group.
Goals: To appreciate computer science as a discipline with an elegant formal foundation with an uncanny number of practical applications.
Special Dates: I will not be in class on the Jewish Holiday of Passover which occurs on Monday April 25. I will announce in class what will occur instead of lecture.
Useful Links: Alan Turing Page
| Assignment_1 | Assignment_2 | Assignment_3 | Assignment_4 |
| Week | Topics | Reading |
| 1 | Introduction: Languages, Grammars, and Automata (Machines). Fundamental connection to computer science. Applications. | 1.1-1.3 |
| 2 | Regular Sets: Finite State Machines, Regular Expressions, and Regular Grammars | 2.1, 3.1 - 3.3 |
| 3 | Nondeterminism and equivalence of NFSM's to DFSM's. Other variants of FSM's | 2.2 - 2.3 |
| 4 | Closure Properties of Regular Sets - a constructive review. | 4.1 |
| 5 | The Pumping Lemma - How to show that a set is not Regular. | 4.3 |
| 6 | Decision Algorithms for FSM's. (Problems whose inputs are FSM's.) Decidability. | 4.2 |
| 7 | Context Free Languages: Context Free Grammars and Applications. | 5.1 - 5.3 |
| 8 | Pushdown Machines - Deterministic versus nondeterministic. | 7.1 - 7.3 |
| 9 | Chomsky Normal Form - Three applications. Equivalence of NPDM and CFL's. | 6.1 - 6.2 |
| 10 | Closure Properties of CFL's and DCFL's. Decision Algorithms for CFL's. Applications to compilers. | 6.3, 8.2 |
| 11 | The CFL Pumping Lemma - Showing that a set is not context free. | 8.1 |
| 12 | Turing Machines and Variants: Multitape, nondeterminism, multidimensional, 2-stack machines. | 9.1 - 9.3 10.1-10.3 |
| 11 | Decidability: The Halting Problem, Post's Correspondence Problem. | 12.1-12.3 |
| 12 | Reductions and more Undecidable problems - CFL equivalence. | 12.4 |
| 13 | Computational Complexity - Measuring the time and space requirements of decidable problems. | 14.1-14.3 |
| 14 | The computational classes P and NP. The concept of an NP-Complete Problems. Reductions revisited. | 14.4 |