Theory of Computation Tutorial

Finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines and decidability.

Theory of Computation (TOC) studies what problems can be solved by a computer, and how efficiently, using abstract mathematical models of computation called automata.

Basic Terminology

TermDefinitionExample
Alphabet (Σ)A finite, non-empty set of symbolsΣ = {0, 1}
StringA finite sequence of symbols from Σ0110
Length |w|Number of symbols in w|0110| = 4
Empty string (ε)The string of length 0|ε| = 0
Σ*All strings over Σ, including ε (Kleene closure){ε, 0, 1, 00, 01, …}
Σ⁺Σ* − {ε} (positive closure){0, 1, 00, …}
LanguageAny subset of Σ*L = {w | w ends in 01}

Chomsky Hierarchy

TypeGrammarLanguageMachineProduction form
3RegularRegularFinite automatonA → aB | a
2Context-freeCFLPushdown automatonA → γ
1Context-sensitiveCSLLinear bounded automatonαAβ → αγβ, |γ| ≥ 1
0UnrestrictedRecursively enumerableTuring machineα → β
Text
Regular ⊂ Context-free ⊂ Context-sensitive ⊂ Recursive ⊂ Recursively enumerable
Recursively enumerable (Type 0) — Turing machineRecursive — TM that always haltsContext-sensitive (Type 1) — Linear bounded automatonContext-free (Type 2) — Pushdown automatonRegular (Type 3) — Finite automaton
Chomsky hierarchy: each class contains the ones inside it
Track your progress through the Theory of Computation course