|
B.Tech. IT 6th Sem Subject: Theory of Computation
UNIT - 1 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.
UNIT - 2 Context Free Grammars (CFG), derivation trees, Simplification normal forms, Chomskey Hierarchy, Regular Grammars, Unrestricted Grammars and Relations Between Classes of languages.
UNIT - 3 Push Down Automata, Definitions relationship between PDA and Context Free Languages, properties of CGL's, Decision Algorithms.
UNIT - 4 Turing Machine, The Turing machine model, Computable languages and functions, Modification of Turing machines, Church' s Hypothesis.
UNIT - 5 Properties of recursive and recursive enumerable languages, Universal Turing machine, Undesirability Post correspondence problem introduction to recursive function theory.
|
