Syllabus Theory of Computation - (314441) Credit Scheme : Examination Scheme : 03 Credits Mid_Semester : 30 Marks End_Semester : 70 Marks Unit I FINITE AUTOMATA Basic Concepts : Symbols, Strings, Language, Formal Language. Finite Automata (FA) : Formal definition and notations for FSM, Concept of state transition diagram and transition table for FA, Construction of DFA, NFA, NFA with epsilon moves. Conversion of NFA with epsilon moves to NFA, Conversion of NFA to DFA, and Conversion of NFA with epsilon moves to DFA, Minimization of FA, Equivalence of FAs, and Applications of FA. Finite State Machine with output : Moore and Mealy machines - Definition, Construction, Inter-Conversion. (Chapter - 1) Unit II REGULAR EXPRESSIONS AND LANGUAGES Regular Expressions (RE) : Definition and Identities of RE, Operators of RE, Equivalence of two regular expressions, Equivalence of regular expressions and regular languages (RL), Conversion of RE to FA using direct method, Conversion of FA to RE using Arden’s theorem, Pumping lemma for RLs, Closure properties of RLs, Applications of Regular Expressions. (Chapter - 2) Unit III CONTEXT FREE GRAMMAR AND LANGUAGE Grammar : Introduction and representation, Chomsky Hierarchy, Formal definition of Regular Grammar(RG), Conversions: LRG to RLG, RLG to LRG, RG to FA, FA to RG. Context Free Grammar (CFG) : Definition of CFG, Derivation tree, sentential forms, Leftmost and Rightmost derivations, Ambiguous Grammar and unambiguous grammar, Context Free Language (CFL). Grammar Simplification, Normal forms : Chomsky Normal Form, Greibach Normal Form. Closure properties of CFL, Pumping lemma for CFL. (Chapter - 3) Unit IV PUSHDOWN AUTOMATA AND POST MACHINE Pushdown Automata(PDA) : Introduction and formal definition of PDA, Construction of Transition diagram and Transition table for PDA, Instantaneous Description of PDA, Equivalence of Acceptance by Final State & Empty stack, Deterministic PDA and Nondeterministic PDA, Context Free Language and PDA, Conversion of CFG to PDA and PDA to CFG. Post Machine (PM) : Definition and construction of Post Machine. (Chapter - 4) Unit V TURING MACHINE Turing Machine (TM) : Formal definition of a Turing machine, Design of Turing machines, Variants of Turing Machines : Deterministic TM, Nondeterministic TM, Multi-tape TM, Universal Turing Machine, Halting problem of TM, Church-Turing thesis, Recursive Languages and Recursively Enumerable Languages, Post Correspondence Problem. (Chapter - 5) Unit VI COMPUTATIONAL COMPLEXITY Decidability : Decidable problems concerning regular languages, Decidable problems concerning context free languages, Un-decidability. Computational Complexity : Measuring Complexity, The Class P, Examples of problems in P, The Class NP, and Examples of problems in NP, Reducibility, Mapping Reducibility, Polynomial Time Reduction and NP Completeness. Satisfiability Problem, NP Completeness of the SAT Problem, Normal Forms for Boolean Expressions, Cook’s theorem, Node-C over Problem. (Chapter - 6)
