### RGTU/RGPV MCA-304 Theory of Computation(TOC) Syllabus MCA 3rd sem Theory of Computation(TOC) Sylabusl

RGTU/RGPV MCA-304 Theory of Computation(TOC) Syllabus
MCA 3rd Sem Theory of Computation(TOC) Syllabus
MCA 3rd - Third Semester Syllabus

MCA-304 Theory of Computation(TOC) Course Contents:

UNIT-I
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.

UNIT-II
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.

UNIT -III
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.

UNIT-IV
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.

UNIT-V
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.

BOOKS
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.

 Mixx it! | More