RCA203 Introduction to Automata Theory & Languages UNIT-1 Basic concepts of Automata Theory: Alphabets, Strings and Languages Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA) – Definition Representation using Transition Tables and State Diagrams Language of DFA and NFA. NFA with ε-transitions Language of NFA with ε-transitions, Equivalence of NFA and DFA UNIT-2 Regular Expressions and Languages: Introduction, Definition of regular expression Kleen’s Theorem, Equivalence of regular expression and Finite Automata Pumping Lemma for regular Languages, Closure properties of Regular Languages Decision properties of Regular Languages Finite Automata with Output: Moore and Mealy Machine Equivalence of Moore and Mealy Machines UNIT-3 Non-Regular Grammars: Definition of Grammar Classification of Grammars, Chomosky's Hierarchy Context Free Grammars (CFG) and Context Free Languages (CFL) - Definition, Examples Derivation trees, Ambiguous Grammars, Simplification of Grammars Normal forms of CFGs: CNF and GNF, Closure properties of CFLs Decision Properties of CFLs, Pumping lemma for CFLs Push Down Automata (PDA): Definition and Description Language of PDA and its applications UNIT-4 Turing Machines: Introduction, Basic Features of a Turing Machine Language of a Turing Machine Variants of Turing Machine: Multitapes, Nondeterministic Turing Machine Universal Turing Machine. Turing Machine as Computer of Integer functions Halting problem of Turing Machine, Church-Turing Thesis UNIT-5 Undecidability: Introduction, Undecidable problems about Turing Machines Rice's Theorem Post's Correspondence problem (PCP) and Modified PCP. Tractable and Intractable Problems: P and NP NPComplete Problems, Introduction to recursive function theory
