RGTU/RGPV MCA-304 Theory of Computation(TOC) Syllabus MCA 3rd sem Theory of Computation(TOC) Sylabusl
MCA-304 Theory of Computation(TOC) Course Contents:
Review of Mathematical Priliminaries : Set, Relations and functions, Graphs and trees, string, alphabets and languages. Principle of induction, predicates and propositional calculus.
Theory of Automation : Definition, description, DFA,NFA, Transition systems,2DFA, equivalence of DFA & NDFA, Regular expressions, regular grammer, FSM with output (mealy and moore models), Minimisation of finite automata.
Formal Languages : Definition & description, Pharse structured grammars & their classification, Chomskey classification of languages, closure properties of families of language, regular grammar, regular set & their closure properties, finite automata, equivalence of FA and regular expression, equivalence of two way finite automata, equivalence of regular expressions.
Context-Free grammar & PDA : Properties unrestricted grammar & their equivalence, derivation tree simplifying CFG, unambiguifying CFG, productions, normal form for CFG, Pushdown automata, 2 way PDA, relation of PDA with CFG, Determinism & Non determinism in PDA & related theorems, parsing and pushdown automata.
Turing Machine : Model, design, representation of TM, language accepted by TM, universal turing machine, determine & non-determinism in TM, TM as acceptor/generator/algorithms, multi- dimentional, multitracks, multitape, Two way infinite tape, multihead, Halting problems of TM.
Computability : Concepts, Introduction to complexity theory, Introduction to undecidaibility, recursively enumerable sets, primitive recursive functions, recursive set, partial recursive sets, concepts of linear bounded Automata, context sensitive grammars & their equivalence.
1. Hopcroft & Ullman “Introduction to Automata theory, languages & Computation” , Narosha Publishing house.
2. Lewish Papadimutrau “Theory of Computation” , Prentice Hall of India, New Delhi.
3. Peter linz, “An Introduction to formal language and automata”, Third edition, Narosa publication.
4. Marvin L. Minskay “Computation : Finite & Infinite Machines”, PHI.
5. Mishra & Chander Shekhar “Theory of Computer Science (Automate, Language & Computations), PHI.
Note : Paper is to be set unit wise with internal choice.