III B.E. (Information Technology)

V SEMESTER

5 IT6.2 THEORY OF COMPUTATION (Elective)

  1. Mathematical Notations and Techniques: Sets, Logic, Functions, Relations and Languages, Inductive Proofs and Recursive Definitions.

  2. Regular  Languages and Finite Automata: Regular Languages and Regular Expression, Finite Automata Kleen’s Theorem. Properties of Regular Languages Pumping Lemma. Non Determisims. Finite Automata with Output and Decision Problem.

  3. Context Free Languages And Pushdown Automata: Context Free Grammars, Union, Concatenation of CFG, Derivation Trees, Ambiguity, Simplified and Normal Forms, Pushdown Automata, Deterministic PDA, PDA for given CFG and CFG for given PDA. Pumping Lemma for context Free Languages and Decision Problems involving Context Free Languages.  

  4. Turing Machines: Definition, Turing Machines as language Acceptor, Combining Turing Machines, Variations of Turing Machines No deterministic Turing Machines, Universal Turing Machines, Recursively Enumerable and Recursive Languages. Unrestricted Grammars and Linear Bounded Automata. The Chomasky Hierarchy.

Recommended Books:

  1. John C. Martin – Introduction of Languages and the Theory of Computation TMH.

  2. John E. Hopcroft, Rajeev Motwani and Ullman- Introduction to Automata Theory, Languages and Computation, Pearson Education Asia.

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