III B.E. (Computer Engg.)

V SEMESTER

5CP5 -THEORY OF COMPUTATION TECHNIQUES

1. MATHEMATICAL NOTATIONS AND TECHNIQUES: Sets Logic, Function, Relations and Languages. Inductive Proofs a Recursive Definitions.

2. REGULAR LANGUAGES AND FINITE AUTOMATA: Regular Languages and Regular Expressions, Finite Automata, Kleen's Theorem. Properties of Regular Languages. Pumping Lemma, Non-Determinism I Finite Automata with Output and Decision Problems.

3. CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA: Context-Free Grammars, Union, Concactation of CFG. Derivation Trees, Ambiguity, Simplified and Normal Forms. Pushdown Automata Deterministic PDA, PDA for given CFG and CFG for given PO Pumping Lemma for Context-Free Languages and Decision Problem involving Context-Free Language.

4. TURNING MACHINES: Definition, Turing Machines as Language Acceptor, Combining Turing Machines, Variations of Turing Machine Nondeterministic Turing Machines. Universal Turing Machine Recursively Enumerable and Recursive languages. Unrestricted Grammers and Turing Machines. Context-Sensitive Grammers Linear-Bounded Automata. The Chomasky Hierarchy.

Recommended Book:

1. JOhl1 E. Hopcroft. Rajeev Mot\vani and J.D. Ullman. Introduction Automata theory, Languages and Computation, Pearson Education A

2. John C. Martin, Introduction to Languages and the Theory Computation, TMH.

3. Cohen. Introduction to Computer Theory, Pearson Education Asia.