Formal Languages and Automata Theory

Work Files

Term Projects

Course Contents

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.

Textbook

Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Addison Wesley, 2001

Weekly Outline

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

Grading

Midterm    20% 
2xQuiz     10 
4xHW       10 
10xCW      10 
Project    15 
Final      35