### Theory of Computation (IT-5001)

**Syllabus**

**UNIT 1: Introduction of the theory of computation**

Introduction of the theory of computation, Finite state automata – description of finite automata, properties of transition functions, Transition graph, designing finite automata, FSM, DFA, NFA, 2-way finite automata, equivalence of NFA and DFA, Mealy and Moore machines. **UNIT 2: Regular grammars**

Regular grammars, regular expressions, regular sets, closure properties of regular grammars, Arden’s theorem, Myhill-Nerode theorem, pumping lemma for regular languages, Application of pumping lemma, applications of finite automata, minimization of FSA. **UNIT 3: Introduction of Context-Free Grammar**

Introduction of Context-Free Grammar - derivation trees, ambiguity, simplification of CFGs, normal forms of CFGs- Chomsky Normal Form and Greibach Normal forms, pumping lemma for CFLs, decision algorithms for CFGs, designing CFGs, Closure properties of CFL’s. **UNIT 4: Introduction of PDA**

Introduction of PDA, formal definition, closure property of PDA, examples of PDA, Deterministic Pushdown Automata, NPDA, conversion PDA to CFG, conversion CFG to PDA. **UNIT 5: Turing machines**

Turing machines - basics and formal definition, language acceptability by TM, examples of TM, variants of TMs – multitape TM, NDTM, Universal Turing Machine, offline TMs, equivalence of single tape and multitape TMs. Recursive and recursively enumerable languages, decidable and undecidable problems – examples, halting problem, reducibility. Introduction of P, NP, NP complete, NP hard problems and Examples of these problems.

**CDGI**