UNIT - I Automata Fundamentals Introduction to formal proof - Additional forms of Proof - Inductive Proofs - Finite Automata - Deterministic Finite Automata - Non-deterministic Finite Automata - Finite Automata with Epsilon Transitions (Chapter - 1) UNIT - II Regular Expressions and Languages Regular Expressions - FA and Regular Expressions - Proving Languages not to be regular - Closure Properties of Regular Languages - Equivalence and Minimization of Automata. (Chapter - 2) UNIT - III Context Free Grammar and Languages CFG - Parse Trees - Ambiguity in Grammars and Languages - Definition of the Pushdown Automata - Languages of a Pushdown Automata - Equivalence of Pushdown Automata and CFG, Deterministic Pushdown Automata. (Chapter - 3) UNIT - IV Properties of Context Free Languages Normal Forms for CFG - Pumping Lemma for CFL - Closure Properties of CFL - Turing Machines - Programming Techniques for TM. (Chapter - 4) UNIT - V Undecidability Non Recursive Enumerable (RE) Language - Undecidable Problem with RE - Undecidable Problems about TM - Post‘s Correspondence Problem, The Class P and NP. (Chapter - 5)
