Formal Languages and Automata Theory CS2004 - NIT Rourkela

Books

The Majority of the course content follows from the first two references.

• Peter Linz, An Introduction to Formal Languages and Automata, Sixth Edition
• Michael Sipser, Introduction to the Theory of Computation, third edition, Course Technology, 2005
• John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman, Introduction to Automata Theory, Languages, and Computation, third edition, Prentice Hall, 2007.
• Harry R Lewis and Christos H Papadimitriou, Elements of the Theory of Computation, second edition, Prentice Hall, 1998.

Tentative Schedule

Class	Topic	Reading	Notebooks and Assignments
1-2	Introduction, Mathematical Preliminaries
3-5	DFA, NFA, Equivalence
6-7	Regular grammar, RE
8-9	Pumping Lemma for regular languages
10	DFA Minimization
11	Moore and Mealy Machine, Equivalence
12-14	CFG, Normal Forms, Parsers
15-16	PDA
17-19	CFG Properties, Pumping Lemma
20	DPDA
21-23	Turing machine, Computation
24-25	TM variations
26-27	Universal Turing Machines
28-30	Decidability, Reductions, Regular CF properties
31-32	Undecidability and Reductions
33-38	Time Complexity, NP Completeness, Reductions, Chomsky Heirarchy