B. Tech. (IT & Mathematical Innovations) - Theory of Computation

Module I: Introduction to Languages and Automata: Formal Grammars and Chomsky Hierarchy, Regular Expression Deterministic and Nondeterministic Finite Automata, Regular Expression, Regular Expression to Finite Automata and vice versa, Arden’s Theorem , Two way Finite Automata, Finite Automata with output, Properties of regular sets, pumping lemma for regular sets, My-Hill-Nerode Theorem .

#TOC-1.1-Formal Grammars and Chomsky Hierarchy Page 1-10 

#TOC-1.2 Finite Automata Page 11-28 

#TOC-1.3 Non-deterministic Finite Automata Page 29-41 

#TOC-1.4 Moore Mealy Machine Page 42-47 

#TOC-1.5 Regular Expression Page 1-16 

Module II: Context Free Grammars and Pushdown Automata: CFG: Formal Definition, Derivation and Syntax trees, Simplification Forms, Ambiguous Grammar, Properties of CFL, Normal Forms (CNF and GNF), Pushdown Automata: Definitions, Relationship between PDA and context free language, Decision Algorithms

# Theory of Computation - Module II - CGF (Click)

# Theory of Computation - Module II & III - PDA & LBA (Click)

Module III: Turing Machine: The Turing Machine Model, Language acceptability of Turing Machine, Design of TM, Variation of TM, Universal TM, Church’s Machine. Recursive and recursively enumerable language, unrestricted grammars, Context Sensitive Language, Linear Bounded Automata (LBA).

# Theory of Computation - Module III - TM (Click)

Module IV: Un-decidability: Turing machine halting Problem, UTM, Undecidable problems for recursive enumerable language, Post correspondence problems (PCP) and Modified Post correspondence problems, Undecidable problems for CFL.

# Theory of Computation - Module IV - Undecidability (Click)

Module V: Computability: Partial and Total Functions, Primitive Recursive functions, Recursive functions.

# Theory of Computation - Module V - Computability (Click)