Classification of automata and formal languages. Finite state machines, regular languages and their limitations. Push-down automata and context-free languages. Normal-form grammars. Context-sensitive languages. Turing machines, halting problem and unsolvability. NP completeness.
Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Addison Wesley, 2001
Feb 12 1. Languages and Automata Feb 19 2. Finite Automata Feb 26 2. Non-deterministic Finite Automata Mar 05 3. Regular Expressions Mar 12 4. Regular Languages -- Quiz Mar 19 5. Context-Free Languages Mar 26 (Midterm) Apr 02 5. Recursive-descent Parsing Apr 09 6. Pushdown Automata Apr 16 Toy language: microJ Apr 25 8. Turing Machines [ek ders] Apr 30 10. Classes P and NP -- Quiz May 07 [class work] May 14 Term project
Midterm 20% 2xQuiz 10 4xHW 10 10xCW 10 Project 15 Final 35