11 notes in this chapter

Theory of Computation Terms MOC

Comprehensive reference for formal language theory, finite automata, computability, decidability, and computational complexity (P vs NP).

Automata & Formal Languages

• Finite Automata (DFA and NFA)
• Regular Expressions and Grammars
• Context-Free Grammars and Pushdown Automata
• Chomsky Hierarchy
• Pumping Lemma

Computability & Decidability

• Turing Machine
• Halting Problem and Decidability
• Church-Turing Thesis
• Turing Completeness

Complexity Theory

• P vs NP Complexity Classes
• Reduction and Completeness

---

How to use this

Use this MOC to understand theoretical limits of computation, language parsing boundaries, and algorithm complexity classifications.

Suggested order if starting from zero

1. Finite Automata (DFA and NFA) → Regular Expressions and Grammars → Context-Free Grammars and Pushdown Automata → Chomsky Hierarchy
2. Pumping Lemma
3. Turing Machine → Church-Turing Thesis → Turing Completeness → Halting Problem and Decidability
4. P vs NP Complexity Classes → Reduction and Completeness