|
MCA 3 SEM. Subject: Theory of Computation
UNIT - 1 Theory of Automata Definition of an automaton, Transition system, Acceptability of a string by FA, Nondeterministic finite state machine, Designing of DFA and NFA, Equivalence of DFA and NFA, Conversion of NFA to DFA, Mealy and Moore models, Minimization of finite automata.
UNIT - 2 Minimization of finite automata. Definition, Languages and their relation Chomsky classification of language, Regular expression, and Finite automaton, Pumping Lemma for regular sets, Application of Pumping lemma, Closure property of regular sets, Regular sets and regular grammar.
UNIT - 3 Context-free Language Context fee language and derivation trees, Ambiguity in context free languages, Simplification of context free languages (left recursion, Unit production elimination, Eliminating null values) Normal forms of context free languages.
UNIT - 4 Pushdown Automation Definition, Acceptance by PDA, Designing PDA, Push down automation and Context free languages, Parsing and Pushdown automata.
UNIT - 5 Turing Machine Turing Machines model, Representation of TM, Languages acceptability by TM, Design of TM. Introduction : Universal Turing Machinesand Halting problem, Linear bounded automata and languages.
|
