Deterministic and non deterministic finite automata, Regular Expression, Two way finite automata, finite automata with output, properties of regular set, pumping lemma, closure properties, My-Hill Nerode Theorem.

Context Free Grammars (CFG), derivation trees, Simplification normal forms, Chomskey Hierarchy, Regular Grammars, Unrestricted Grammars, Relations Between Classes of languages.

Push Down Automata, Definitions relationship between PDA and Context Free Languages, properties of CGL's Decision Algorithms.

Turing Machine, The Turing machine model, Computable languages and functions, Modification of Turing machines, Church's Hypothesis.

Properties of recursive and recursive enumerable languages, Universal Turing machine, Undesirability Post correspondence problem, introduction to recursive function theory.