Syllabus Theory of Computation - (310242) Credit : Examination Scheme : 03 Mid-Sem (TH) : 30 Marks End-Sem (TH) : 70 Marks Unit I Formal Language Theory and Finite Automata Finite Automata (FA) : An informal picture of FA, Finite State Machine (FSM), Language accepted by FA, Definition of Regular Language. FA without output : Deterministic and Nondeterministic FA (DFA and NFA), epsilon- NFA and inter-conversion. Minimization of DFAs. FA with output : Moore and Mealy machines -Definition, models, inter-conversion. (Chapter - 1) Unit II Regular Expressions (RE) Introduction, Operators of RE, Precedence of operators, Algebraic laws for RE, Language to Regular Expressions, Equivalence of two REs. Conversions : RE to NFA, DFA, DFA to RE using Arden’s theorem, Pumping Lemma for Regular languages, Closure and Decision properties of Regular languages. Myhill-Nerode theorem. (Chapter - 2) Unit III Context Free Grammar (CFG) and Context Free Language(CFL) Basic Elements of Grammar, Formal Definition of Context Free Grammar, Sentential form, Derivation and Derivation Tree/ Parse Tree, Context Free Language (CFL), Ambiguous Grammar, writing grammar for language. Simplification of CFG : Eliminating Є-productions, unit productions, useless production, and useless symbols. Normal Forms : Chomsky Normal Form, Greibach Normal Form, Pumping Lemma for CFG, Closure properties of CFL, Decision properties of CFL, Chomsky Hierarchy, Cock-Younger-Kasami Algorithm. (Chapter - 3) Unit IV Pushdown Automata (PDA) Introduction, Formal definition of PDA, Equivalence of Acceptance by Final State and Empty stack, Non-deterministic PDA (NPDA), PDA and Context Free Language, Equivalence of PDA and CFG, PDA vs CFLs. Deterministic CFLs. (Chapter - 4) Unit V Turing Machines (TM) Turing Machine Model, Formal definition of Turing Machines, Language Acceptability by Turing Machines, Design of TM, Description of TM, Techniques for TM Construction, Computing function with Turing Machine, Variants of Turing Machines, Halting Problem of TM, Halting vs Looping, A Turing-unrecognizable language, Reducibility, Recursion Theorem. The Model of Linear Bounded Automata. (Chapter - 5) Unit VI Computability and Complexity Theory Computability Theory : Decidable Problems and Un-decidable Problems, Church-Turing Thesis. Reducibility : Undecidable Problems that is recursively enumerable, A Simple Un-decidable problem. Complexity Classes : Time and Space Measures, The Class P, Examples of problems in P, The Class NP, Examples of problems in NP, P Problem Versus NP Problem, NP-completeness and NP-hard Problems. (Chapter - 6)
