Theory of Computation

Course Overview

Pre-requisites

Computer Architecture, Discrete Mathematical Structures

Textbook & References

Theory of Computation: Automata, Formal Languages, Computation, and Complexity

Course Deployment

CS222 – Course Deployment Document

Module 1: Finite Automata & Regular Languages

• Syllabus: Theory of Computation
• Assessment & References
• Introduction to Theory of Computation
• Deterministic Finite Automata (DFA)
• Regular Expressions
• Nondeterministic Finite Automata (NFA)
• Minimization of Finite Automata
• Closure Properties of Regular Languages
• Pumping Lemma for Regular Languages

Module 2: Context-Free Languages, Grammars & Pushdown Automata

• Context-Free Languages and Grammars
• Normalization of Context-Free Grammars
• Closure Properties and Ambiguity in CFLs
• Pumping Lemma for Context-Free Languages
• Pushdown Automata
• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4: CFGs & CFLs

Module 3: Turing Machines, Chomsky Hierarchy & Complexity Theory

• Introduction to Turing Machines
• TM as Function Computer
• Variants of Turing Machines
• Computational Complexity of TMs
• Universal Turing Machine
• Turing-Recognizable Languages
• Recursive & Recursively Enumerable Languages
• Decidability and Undecidability
• Complexity Classes (P, NP, NP-Complete)
• Rice’s Theorem