MCA-304 THEORY OF COMPUTATION SYLLABUS

RAJIV GANDHI PROUDYOGIKI VISHWAVIDYALAYA

  (University of Technology of Madhya Pradesh)

COURSE OF STUDY AND SCHEME OF EXAMINATION

MASTER OF COMPUTER APPLICATIONS (MCA)

W.E.F. 2005-2006

MCA-304 THEORY OF COMPUTATION SYLLABUS

 

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 tuning machine, determine & non-determinism in TM, TM as acceptor/generator/algorithms, multidimentional, 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.