THEORY OF AUTOMATA & FORMAL LANGUAGES
L T P
3 1 0
Unit I (8L)
Introduction to defining language, Kleene closures, Arithmetic expressions, defining grammar,
Chomsky hierarchy, Finite Automata (FA), Transition graph, generalized transition graph.
Unit II (8L)
Nondeterministic finite Automata (NFA), Deterministic finite Automata (DFA), Construction of
DFA from NFA and optimization, FA with output: Moore machine, Mealy machine and
Equivalence, Applications and Limitation of FA.
Unit III (8L)
Arden Theorem, Pumping Lemma for regular expressions, Myhill-Nerode theorem, Context
free grammar: Ambiguity, Simplification of CFGs, Normal forms for CFGs, Pumping lemma
for CFLs, Decidability of CFGs, Ambiguous to Unambiguous CFG.
Unit IV (8L)
Push Down Automata (PDA): Description and definition, Working of PDA, Acceptance of a
string by PDA, PDA and CFG, Introduction to auxiliary PDA and Two stack PDA.
Unit V (8L)
Turing machines (TM): Basic model, definition and representation, Language acceptance by
TM, TM and Type – 0 grammar, Halting problem of TM, Modifications in TM, Universal TM,
Properties of recursive and recursively enumerable languages, unsolvable decision problem,
undecidability of Post correspondence problem, Church’s Thesis, Recursive function theory.