Syllabus Theory of Computation - (BE05000271) Total Credits Assessment Pattern and Marks Total Marks TH/30 Theory Tutorial / Practical ESE (E) PA (M) PA (I) PBL (I) ESE (V) 03 70 30 20 30 50 200 Unit No. Content 1 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, Backus-Naur Form(BNF), Chomsky 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 Un-decidability : A Language That Cannot Be Accepted, and a Problem That Cannot Be Decided, Non-Recursive Enumerable (RE) Language - Undecidable Problem with RE - Undecidable Problems about TM - Undecidable Problems Involving Context-Free Languages, Post Correspondence Problem, The Class P and NP. (Chapter - 7)
