Theory of Computation (IT-503 (A))-Information Technology (V-Semester) | RGPV

---

• Syllabus

• Syllabus - Theory of Computation (IT-503 (A))

• UNIT I

• Introduction of the theory of computation
• Finite state automata
• Equivalence of NFA and DFA
• Mealy and Moore machines

• UNIT II

• Regular grammars, expressions, and sets
• Closure properties and theorems
• Pumping lemma for regular languages
• Applications and minimization of FSA

• UNIT III

• Introduction of Context-Free Grammar
• Pumping lemma for CFLs
• Decision algorithms for CFGs
• Designing CFGs and closure properties of CFL’s

• UNIT IV

• Introduction of PDA
• Deterministic Pushdown Automata and NPDA
• Conversion between PDA and CFG

• UNIT V

• Turing machines
• Variants of TMs
• Recursive and recursively enumerable languages
• Decidable and undecidable problems
• Introduction of P, NP, NP complete, NP hard problems