Verify Account

SYLLABUS

UNIT-I

INTRODUCTION Basics of set theory, Relations on sets, Deductive proofs, Reduction to definitions, Other theorem forms, Proving equivalences about sets, The Contrapositive, Proof by contradiction, Counter examples, Inductive proofs, Alphabets, Strings, Languages, Problems, Grammar formalism, Chomsky Hierarchy. FINITE AUTOMATA An Informal picture of Finite Automata, Deterministic Finite Automata (DFA), Non Deterministic Finite Automata (NFA), Applying FA for Text search, Finite Automata with Epsilon transitions (∈-NFA or NFA-∈ ), Finite Automata with output, Conversion of one machine to another, Minimization of Finite Automata, Myhill-Nerode Theorem.

UNIT-II

REGULAR LANGUAGES Regular Expressions (RE), Finite Automata and Regular Expressions, Applications of Regular Expressions, Algebraic laws for Regular Expressions, The Arden’s Theorem, Using Arden’s theorem to construct RE from FA, Pumping Lemma for RLs, Applications of Pumping Lemma, Equivalence of Two FAs, Equivalence of Two REs, Construction of Regular Grammar from RE, Constructing FA from Regular Grammar, Closure properties of RLs, Decision problem’s of RLs, Applications of REs and FAs.

UNIT-III

CONTEXT FREE GRAMMARS AND LANGUAGES Definition of Context Free Grammars (CFG), Derivations and Parse trees, Ambiguity in CFGs, Removing ambiguity, Left recursion and Left factoring, Simplification of CFGs, Normal Forms, Linear grammars, Closure properties for CFLs, Pumping Lemma for CFLs, Decision problems for CFLs, CFG and Regular Language.

UNIT-IV

PUSH DOWN AUTOMATA (PDA) Informal introduction, The Formal definition, Graphical notation, Instantaneous description, The Languages of a PDA, Equivalence of PDAs and CFGs, Deterministic Push Down Automata, Two Stack PDA.

UNIT-V

TURING MACHINES AND UNDECIDABILITY Basics of Turing Machine (TM), Transitional representation of TMs, Instantaneous description, Non Deterministic TM, Conversion of Regular Expression to TM, Two stack PDA and TM, Variations of the TM, TM as an integer function, Universal TM, Linear Bounded Automata, TM Languages, Unrestricted grammar, Properties of Recursive and Recursively enumerable languages, Undecidability, Reducibility, Undecidable problems about TMs, Post’s Correspondence Problem(PCP), Modified PCP.