Review of Mathematical Theory: Sets, Functions, Logical statements, Proofs, Relations, Languages, Principal of Mathematical Induction, Strong Principle, Recursive Definitions, Structural Induction. (Chapter - 1) 2. Regular Languages and Finite Automata: Regular Expressions, Regular Languages, Application of Finite Automata, Automata with output - Moore machine & Mealy machine, Finite Automata, Memory requirement in a recognizer, Definitions, union- intersection and complement of regular languages, Non Deterministic Finite Automata, Conversion from NFA to FA, - Non Deterministic Finite Automata, Conversion of NFA - to NFA, Kleene’s Theorem, Minimization of Finite automata, Regular And Non Regular Languages - pumping lemma. (Chapter - 2) 3. Context free grammar (CFG): Definitions and Examples, Unions Concatenations And Kleene’s of Context free language, Regular Grammar for Regular Language, Derivations and Ambiguity , Unambiguous CFG and Algebraic Expressions, BacosNaur Form (BNF), Normal Form - CNF. (Chapter - 3) 4. Pushdown Automata, CFL And NCFL: Definitions, Deterministic PDA, Equivalence of CFG and PDA & Conversion, Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL. (Chapter - 4) 5. Turing Machine (TM): TM Definition, Model Of Computation, Turing Machine as Language Acceptor, TM that Compute Partial Function, Church Turning Thesis, Combining TM, Variations Of TM, Non Deterministic TM, Universal TM, Recursively and Enumerable Languages, Context sensitive languages and Chomsky hierarchy. (Chapter - 5) 6. Computable Functions: Partial - Total - Constant Functions, Primitive Recursive Functions, Bounded Mineralization, Regular function, Recursive Functions, Quantification, Minimalization, and µ-Recursive Functions, All Computable Functions Are µ-Recursive. (Chapter - 6) 7. Undecidability: A Language That Can’t Be Accepted, and a Problem That Can’t Be Decided , Non Recursive Enumerable (RE) Language - Undecidable Problem with RE - Undecidable Problems about TM - Undecidable Problems Involving Context-Free Languages, Post‘s Correspondence Problem, The Class P and NP. (Chapter - 7)
