>>Send ur suggestion to Mynotes Tab
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.
Text Books:
1. Hopcroft, Ullman, “Introduction to Automata Theory, Language and Computation”, Nerosa Publishing House, 3rd Edition :
Direct Link to the Book
2. K.L.P. Mishra and N.Chandrasekaran, “Theory of Computer Science(Automata, Languages and Computation)”, PHI, 3rd Edition :
Direct Link to the Book
Reference Books:
1. Martin J. C., “Introduction to Languages and Theory of Computations”, TMH
2. Papadimitrou, C. and Lewis, C.L., “Elements of theory of Computations”, PHI
3. Cohen D. I. A., “Introduction to Computer theory”, John Wiley & Sons
4. Kumar Rajendra, “Theory of Automata (Languages and Computation)”, PPM