1.Introduction to Finite Automata: Introduction to Finite Automata, Central Concepts of Automata Theory, Deterministic Finite Automata (DFA), Nondeterministic Finite Automata (NFA), Finite Automata with Epsilon Transition. (Chapter - 1) 2.Regular Expressions and Languages: Regular Expressions, Finite Automata and Regular Expressions, Applications of Regular Expressions, Proving Languages Not to Be Regular, Closure Properties of Regular Languages, Equivalence and Minimization of Automata – Pumping Lemma. (Chapter - 2) 3.Context Free Grammars and Languages Parse Trees: Applications of Context Free Grammars, Ambiguity in Grammars and Languages, Eliminating Useless Symbols, Computing the Generating and Reachable Symbols, Eliminating Epsilon Productions, Eliminating Unit Productions, BacosNaur Form (BNF), Chomsky Normal Form (CNF). (Chapter - 3) 4.Pushdown Automata, CFL and NCFL: Definition of the Pushdown Automata (PDA), The Languages of a PDA, Equivalence of PDA’s and CFG’s,Deterministic Pushdown Automata , The Pumping Lemma for Context Free Languages , Closure Properties of Context Free Languages, Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL (Chapter - 4) 5.Turing Machine (TM): Problems That Computers Cannot Solve, The Turing Machine, Programming Techniques for Turing Machines, Extensions to the Basic Turing Machine, Restricted Turing Machines, Turing Machines and Computers, Definition of Post’s Correspondence Problem, A Language That Is Not Recursively Enumerable, An Undecidable Problem That Is RE, Context sensitive languages and Chomsky hierarchy, Other Undecidable Problems. (Chapter - 5) 6.Computable Functions: Partial, total, constant functions, Primitive Recursive Functions, Bounded Mineralization, Regular function, Recursive Functions. (Chapter – 6)
