Theory of Computation

Syllabus

1. Module 1

   Formal Languages

   • Alphabets, Strings, and Languages
   • Operations on Languages
   • Grammars and Derivations
   • Decision Problems and Encodings

2. Module 2

   Finite Automata

   • Deterministic Finite Automata
   • Nondeterministic Finite Automata
   • Epsilon Transitions
   • Closure Properties of Regular Languages

3. Module 3

   Regular Expressions and Regular Languages

   • Regular Expressions
   • Equivalence of Automata and Regular Expressions
   • State Minimization
   • The Pumping Lemma for Regular Languages

4. Module 4

   Context-Free Languages

   • Context-Free Grammars
   • Parse Trees and Ambiguity
   • Normal Forms
   • Closure Properties of Context-Free Languages

5. Module 5

   Pushdown Automata

   • Pushdown Automata
   • Equivalence of PDAs and CFGs
   • Deterministic Context-Free Languages
   • The Pumping Lemma for Context-Free Languages

6. Module 6

   Turing Machines

   • The Turing-Machine Model
   • Variants and Robustness
   • Recognizable and Decidable Languages
   • Universal Computation and Encodings

7. Module 7

   Decidability

   • Deciders and Recognizers
   • Mapping Reductions
   • The Halting Problem
   • Rice’s Theorem and Semantic Properties

8. Module 8

   Complexity Foundations

   • Time and Space Complexity
   • Polynomial Time and Efficient Computation
   • Nondeterminism and NP
   • Certificates and Verification

9. Module 9

   NP-Completeness

   • Cook–Levin and Satisfiability
   • Polynomial-Time Reductions
   • Classic NP-Complete Problems
   • Designing Correct Reduction Gadgets

10. Module 10

    Beyond NP

    • Space Complexity and PSPACE
    • Randomized Complexity Classes
    • Approximation and Hardness of Approximation
    • The Church–Turing Thesis and Limits of Models