11-12-2012, 12:01 PM
THEORY OF COMPUTATION ® 2 – 1 – 0
THEORY OF COMPUTATION.docx (Size: 11.56 KB / Downloads: 20)
Module 1
Introduction to theory of computation, Finite state automata – description of finite automata, Properties of transition functions, Designing finite automata, NFA, 2 way finite automata, equivalence of NFA and DFA, Mealy and Moor machine, finite automata with epsilon moves, Regular sets and regular grammars, regular expressions, pumping lemma for regular languages, closure properties of regular sets and regular grammars, Application of finite automata, Decision algorithms for regular sets, Minimization of FSA.
Module 2
Chomsky classification of languages, CFGs, Derivation trees, ambiguity, simplification of CFLs, normal forms of CFGs, pumping lemma for CFGs, decision algorithms for CFGs, designing CFGs, PDA – formal definition, examples of PDA, equivalence with CFGs, PDA and CFG, Chomsky hierarchy.
Module 3
Turing machines basics and formal definition, Language acceptability by TM, examples of TM, variants of TMs –multitape TM, NDTM, Universal Turing Machine, offline TMs, Equivalence of single tape and multitape TMs, recursive and recursively enumerable languages, decidable and undecidable problems – examples, halting problem, reducibility.