MS-11 Theory of Computation
Unit – I
Formal Languages, Need for formal computational models, Non-computability and examples of non-
computable problems, diagonal argument and Russel's paradox, Chomsky hierarchy of formal languages,
Regular languages, Regular sets, regular grammars, computable and non-computable problems.
Unit – II
Deterministic and Non-Deterministic finite automata, equivalence of deterministic and non-deterministic
finite automata, Kleen's characterization theory for sets accepted by finite automata, finite state machines and
their relations to combinatorial switching circuits, complexity, State equivalence and state minimization of
finite automata, pumping lemma, Algebra decomposition and structure theory.
Unit – III
Context Free Grammers, Chomsky & Greibiech normal form theorems, Self embedding, Equivalence of
context free languages and sets accepted by non-deterministic push down store automata, pushdown
automata, closure properties of context free languages, Ambiguity, Ambiguous grammars, Parsing: Early's,
Cook-Kasami-Young, Tomito's, top-down and bottom-up methods, Restrictions of push-down automata.
Unit – IV
Linear bounded automata (LBA): Power of LBA, closure properties
Turing machine (TM): one-tape, Multitape Turing machines and related formalism for recognition, Time and
space complexity in terms of TM, Construction of TM for various problems, Unsolvability of the halting
problem, reduction of post correspondence problem to the halting problem, Undecidable properties of
grammars. Recursive and recursively enumerable language.
Unit – I
Formal Languages, Need for formal computational models, Non-computability and examples of non-
computable problems, diagonal argument and Russel's paradox, Chomsky hierarchy of formal languages,
Regular languages, Regular sets, regular grammars, computable and non-computable problems.
Unit – II
Deterministic and Non-Deterministic finite automata, equivalence of deterministic and non-deterministic
finite automata, Kleen's characterization theory for sets accepted by finite automata, finite state machines and
their relations to combinatorial switching circuits, complexity, State equivalence and state minimization of
finite automata, pumping lemma, Algebra decomposition and structure theory.
Unit – III
Context Free Grammers, Chomsky & Greibiech normal form theorems, Self embedding, Equivalence of
context free languages and sets accepted by non-deterministic push down store automata, pushdown
automata, closure properties of context free languages, Ambiguity, Ambiguous grammars, Parsing: Early's,
Cook-Kasami-Young, Tomito's, top-down and bottom-up methods, Restrictions of push-down automata.
Unit – IV
Linear bounded automata (LBA): Power of LBA, closure properties
Turing machine (TM): one-tape, Multitape Turing machines and related formalism for recognition, Time and
space complexity in terms of TM, Construction of TM for various problems, Unsolvability of the halting
problem, reduction of post correspondence problem to the halting problem, Undecidable properties of
grammars. Recursive and recursively enumerable language.
Text Books
1 Kamla kirtheivshan & Rama R, Automata theory & Computation, PEARSON, 1/e
2 Peter Linz, An introduction to formal language & automata, Jones & Bartlete pub. 5/e
Reference Books:
1. Hopcroft,J.E.&Ullman,J.D. Formal languages and their relation to Automata, Addison-Wasley
2. E.V.Krishnamurthy, Introductory Theory of Computer Science Ease-West press Pvt. Ltd.
3. Salomma, A.K. Formal languages, Academic press.
4. Lewis, H.R.& Papadimitrious, C.H. Elements of the Theory of Computation.PHI.
5. Zoha Mauna, Mathematical Theory of Computation, Wiley Inter-science.
No comments:
Post a Comment