Unit – I
Introduction to defining language, Kleene closures, Arithmetic expressions, defining grammar, Chomsky hierarchy, Finite Automata (FA), Transition graph, generalized transition graph.
Unit – II
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
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
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
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, Godel Numbering.
Text Books and References:
Hopcroft, Ullman, “Introduction to Automata Theory, Language and Computation”, Nerosa Publishing House
2. K.L.P. Mishra and N.Chandrasekaran, “Theory of Computer Science(Automata,
Languages and Computation)”, PHI
3. Martin J. C., “Introduction to Languages and Theory of Computations”, TMH
4. Papadimitrou, C. and Lewis, C.L., “Elements of theory of Computations”, PHI
5. Cohen D. I. A., “Introduction to Computer theory”, John Wiley & Sons
6. Kumar Rajendra, “Theory of Automata (Languages and Computation)”, PPM