MCA-304 Theory of Computation:

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, unamb-productions, normal form for CFG, Pushdown automata, 2Îiguifying CFG,

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

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------