Alphabets, Strings, Grammar and Languages, Chomsky Hierarchy, Finite Automata, Representation of FA, Types of Finite Automata, Conversion of NFA into DFA, Equivalence of DFA and NFA, Finite Automata with Epsilon transitions, Finite Automata with output, Conversion of one machine to another, Minimization of Finite Automata, Myhill-Nerode Theorem, Applications and Limitation of Finite Automata.

Regular Expressions (RE), Identity Rules, The Arden‘s Theorem, Applications of Pumping Lemma, Equivalence of Two FAs, Equivalence of Two REs, Construction of Regular Grammar from RE, Closure properties of RLs, Constructing FA from Regular Grammar, Pumping Lemma for RLs, Decision problems of RLS, Applications of REs and FAs.

Context Free Grammar, Leftmost and Rightmost Derivations, Parse Trees, Ambiguous Grammars, Simplification of Context Free Grammars, Left recursion and Left factoring, Linear Grammar,Conversion Methods of Linear Grammar,Normal Forms for Context Free Grammars, Pumping Lemma for CFLs, Closure Properties, Applications of Context Free Grammars.

Pushdown Automata, Instantaneous Description, Language Acceptance of pushdown Automata, Design of Pushdown Automata, Deterministic and Non - Deterministic Pushdown Automata, Conversion of CFG to PDA and PDA to CFG, Equivalence of Pushdown Automata, Two Stack Pushdown Automata.

Turing Machine, Instantaneous Descriptions, Representation of TMs, Language Acceptance of a Turing Machine, Design of Turing Machines, Variations of Turing Machines, Church‘s Thesis, Universal Turing Machine, Linear Bounded Automata, TM Languages, Unrestricted grammar, Properties of Recursive and Recursively enumerable languages, Un-decidability, Reducibility, Un- decidable problems about TMs, Post Correspondence Problem (PCP), Modified PCP.