Theory of Automata and Formal Languages

Unit I

Basic Concepts and Automata Theory: Introduction to Theory of Computation — Automata, Computability and Complexity, Alphabet, Symbol, String, Formal Languages, Deterministic Finite Automaton (DFA) — Definition, Representation, Acceptability of a String and Language, Non-Deterministic Finite Automaton (NFA), Equivalence of DFA and NFA, NFA with ε-Transition, Finite Automata with Output — Moore and Mealy Machines and Their Equivalence, Minimization of Finite Automata.

Unit II

Regular Expressions and Languages: Regular Expressions, Transition Graph, Kleene's Theorem, Finite Automata and Regular Expressions — Arden's Theorem, Algebraic Method, Closure Properties of Regular Languages, Pigeonhole Principle, Pumping Lemma and its Applications, Decidability — Decision Properties, Finite Automata and Regular Languages.

Unit III

Regular and Non-Regular Grammars: Context Free Grammar (CFG) — Definition, Derivations, Languages, Derivation Trees and Ambiguity, Regular Grammars — Right Linear and Left Linear, Conversion of FA into CFG and Regular Grammar into FA, Simplification of CFG, Normal Forms — CNF and GNF, Chomsky Hierarchy, Programming Problems on CFG Properties.

Unit IV

Push Down Automata and Context Free Languages: Nondeterministic Pushdown Automata (NPDA) — Definition, Moves, Language Accepted, Deterministic Pushdown Automata (DPDA) and DCFL, PDA for CFLs, CFGs for PDA, Two-Stack PDA, Pumping Lemma for CFL, Closure Properties and Decision Problems of CFL.

Unit V

Turing Machines and Recursive Function Theory: Basic Turing Machine Model, Representation, Language Acceptability, Construction Techniques, Modifications, TM as Computer of Integer Functions, Universal Turing Machine, Linear Bounded Automata, Church's Thesis, Recursive and Recursively Enumerable Languages, Halting Problem, Post's Correspondence Problem, Introduction to Recursive Function Theory.