Theory of Computation for SPPU 19 Course (TE – SEM V – IT- 314441)

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 IIRegular 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 IIIContext 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 IVPushdown 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. Unit V Turing Machine Unit VI Computational Complexity