Unit-1
Introduction of Automata Theory: Examples of automata machines, Finite Automata as a language acceptor and translator, Moore machines and mealy machines, composite machine, Conversion from Mealy to Moore and Moore to Mealy.
Unit-2
Types of Finite Automata: Non Deterministic Finite Automata (NDFA), Deterministic finite automata machines, conversion of NDFA to DFA, minimization of automata machines, regular expression, Arden’s theorem. Meaning of union, intersection, concatenation and closure, 2 way DFA.
Unit-3
Grammars: Types of grammar, context sensitive grammar, and context free grammar, regular grammar. Derivation trees, ambiguity in grammar, simplification of context free grammar, conversion of grammar to automata machine and vice versa, Chomsky hierarchy of grammar, killing null and unit productions. Chomsky normal form and Greibach normal form.
Unit-4
Push down Automata: example of PDA, deterministic and non-deterministic PDA, conversion of PDA into context free grammar and vice versa, CFG equivalent to PDA, Petrinet model.
Unit-5
Turing Machine: Techniques for construction. Universal Turing machine Multitape, multihead and multidimensional Turing machine, N-P complete problems. Decidability and Recursively Enumerable Languages, decidability, decidable languages, undecidable languages, Halting problem of Turing machine & the post correspondence problem.
RECOMMENDED BOOKS
- Introduction to Automata Theory Language & Computation, Hopcroft& Ullman, Narosa Publication.
- Element of the Theory Computation, Lewis &Christors, Pearson.
- Theory of Computation, Chandrasekhar & Mishra, PHI.
- Theory of Computation, Wood, Harper & Row.
- Introduction to Computing Theory, Daniel I-A Cohen, Wiley