UNIT–I
Introduction: Finite state automata, Non-deterministic finite state automata, FA with-transitions, Regular expressions, FA with outputs, Applications of FA. Properties of regular sets-Pumping Lemma, Closure properties, Myhill-Nerode Theorem, Minimization of FA, Decision Algorithms.
UNIT–II
Context-Free Grammars and Languages: Derivations, Parse-trees, Ambiguity in Grammars and Languages. Pushdown Automata–Definitions, The languages of PDA, Equivalence of PDAs and CFGs, Deterministic Pushdown Automata (DPDA).
UNIT-III
Properties of CFLs: Normal forms for CFGs, Pumping Lemma, Closure properties, Decision algorithms, Deterministic Context-Free Languages, Predicting machines, Decision properties, LR(0) grammars, LR(0) and DPDA,LR(k) grammars
UNIT-IV
Turing Machines: Introduction, Computational Languages, and Functions, Techniques for construction of Turing machines. Modifications of TM, TM as an enumerator, Restricted TM.
UNIT–V
Undecidability: Recursive and Recursively enumerable languages, UTM and undecidable problem, Rice Theorem, Post’s correspondence problem. Chomsky’s Hierarchy–Regular grammars, Unrestricted grammar, CSL, Relationship between classes of languages.
Suggested Readings:
1. John E. Hopcroft, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation,Narosa,1979
2. Zvi Kohavi, Switching and Finite Automata Theory, TMH,1976