Syllabus
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 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.
Previous year question papers
