Eleven topics, each with a written explanation, a hand-drawn diagram, and a pointer to the
place in Sipser's textbook and the matching MIT lecture video. Read it top-to-bottom in one
sitting and you have the vocabulary for our entire semester.
A finite alphabet Σ is just a finite collection of symbols (the simplest is Σ = {0, 1}).
A string is a finite sequence of symbols from Σ. The empty string is ε.
The set of all finite strings over Σ is written Σ*. A language
is any subset L ⊆ Σ*.
An alphabet is a finite set. Σ* is the (infinite) set of all finite strings you can form. A language is any subset of Σ*. Every algorithmic question in this course is "is this string in this language?".
Set operations you'll see constantly
Four set operations. Symmetric difference (A △ B) — the striped region — is the key to the EQDFA algorithm in Module 1.
Function classification
Injective = no collisions; surjective = nothing left over; bijective = both. Bijections are how we'll prove two infinite sets are "the same size" (used in Cantor's diagonal argument).
A DFA is the simplest computing model: finitely many states, a read-only input head that moves
left-to-right, and a deterministic transition function. Given a string, the DFA either accepts
or rejects after reading the last symbol.
A DFA is a 5-tuple. Double circle = accept state. The string "0101" traces q₀ → q₁ → q₁ → q₀ → q₀ — ends in accept state, so accepted.
An NFA can be in multiple states at once, has ε-transitions (free moves), and several edges
can leave a state with the same label. Despite seeming more powerful, every NFA can be
converted to a DFA via the subset construction — at the cost of
exponentially many states.
Subset construction: every DFA state is a subset of NFA states. For an NFA with n states, the equivalent DFA can have up to 2ⁿ states — exponential blow-up, but always finite.
Regular expressions describe regular languages with a compact algebra: ∅, ε, single
characters, union (∪), concatenation (·), Kleene star (*). Kleene's theorem
says regex, NFA, and DFA all recognize exactly the same class of languages — the regular
languages.
The three faces of regular languages are interchangeable. Regex is the algebraic, NFA the nondeterministic-machine, and DFA the deterministic-machine view.
The pumping lemma is how we prove a language is not regular. Every long
enough string in a regular language must have a "pump" — a substring that can be repeated
any number of times and still stay in the language.
If the language is regular and w is long enough, w decomposes as xyz with a pumpable middle. To prove a language is NOT regular: assume it is, pick a long string, then exhibit some i for which xyⁱz is not in the language.
Classic example. The language {0ⁿ1ⁿ : n ≥ 0} is not regular. Proof sketch: take
w = 0ᵖ1ᵖ. Whatever x, y, z gives |xy| ≤ p, the pump y lies entirely in the 0s. Pumping makes
the 0-count differ from the 1-count, so the result is not in L.
A CFG is a set of production rules that rewrite variables into strings of
variables and terminals. The language of the grammar is all strings of terminals derivable
from the start variable. CFGs describe nested / matched structure (parentheses,
palindromes, programming-language syntax).
A CFG generates strings by recursively applying rules. The parse tree captures the derivation: leaves spell out the terminal string left-to-right. CFGs are strictly more powerful than regex — they can express nested structure regex cannot.
Chomsky Normal Form (CNF)
Every CFG can be converted to CNF, where every rule has either two variables on the right
(A → BC) or a single terminal (A → a). CNF is what the CYK parsing
algorithm needs (used in Module 1's ACFG widget).
A PDA = finite-state automaton + an unbounded LIFO stack. The stack lets it remember unbounded
context, which is exactly the power needed for context-free languages. CFG ⇔ PDA equivalence
is the bridge between grammars and machines.
A PDA reads input left-to-right, can push or pop the stack on each step, and accepts when its state is an accept state at the end of the input (or, in some variants, when the stack is empty). PDAs recognize exactly the context-free languages.
A Turing machine is the full computational model: a two-way read/write tape (unbounded in
both directions, conceptually), a head that can move left or right one cell per step, and a
finite control with accept and reject states. Everything in our course from
Lecture 2 onward is about Turing machines.
A TM is a 7-tuple. The transition function δ reads (state, current cell), and prescribes (new state, write symbol, move L or R). When δ enters qaccept or qreject, the machine halts. Otherwise it might run forever.
A surprisingly robust feature of Turing machines: many variations look more powerful, but in
fact recognize exactly the same class of languages. The cost is sometimes polynomial time
or constant tape blow-up, but the class is unchanged.
Multi-tape and nondeterministic TMs can be simulated by single-tape deterministic ones, but at a polynomial / exponential time cost. They are equally powerful, but not equally efficient — this is what motivates complexity classes.
The Church-Turing thesis is an informal claim, not a theorem: everything that can be
computed by an algorithm can be computed by a Turing machine. It lets us interchange
"algorithm", "program", "procedure", and "Turing machine" in proofs.
The Church-Turing thesis isn't a theorem we prove; it's a working assumption that has never been refuted in 90 years. It lets us describe TMs informally in English and trust the formal construction exists.
A Turing machine is just a finite table of transitions. So you can encode it as a binary
string ⟨M⟩. Once a TM is data, you can feed it as input to another TM — this is the
foundation of the universal TM (Lecture 2) and every undecidability proof
we will see.
Once M is a string, we can write down questions like "does M accept w?" as language membership questions about pairs ⟨M, w⟩. This is what makes ATM = {⟨M, w⟩ : M accepts w} a well-defined language.
🎧 Narration
§ 11 · Decidable vs Turing-recognizable
This is the single most important distinction in the entire course. A TM that
decides a language always halts with the correct yes/no answer. A TM that
only recognizes a language accepts every yes-instance but may loop forever
on no-instances.
A decider gives a verdict for every input. A recognizer may loop forever on no-instances. The famous ATM language is recognizable (use a universal TM) but not decidable (Cantor diagonal kills the decider) — this is the gap that drives the entire undecidability story.
Day-one checklist · prove you're ready
Before the first lecture, every student should be able to:
Draw a DFA for "strings with an even number of 0s" and trace a 6-character input through it.
Convert an NFA with ε-transitions into an equivalent DFA via subset construction.
Write a regex for "strings ending in 01" and an equivalent NFA.
Prove {0ⁿ1ⁿ} is not regular using the pumping lemma.
Write a CFG for balanced parentheses and parse "(())" via the rules.
Describe a Turing machine that decides {0ⁿ1ⁿ} — by hand, transition by transition.
Explain in one sentence what "Turing-recognizable but not decidable" means.
Encode a small Turing machine as a binary string ⟨M⟩ (rough sketch is fine).
If you can do all eight, you're ready. If two or more feel impossible, spend a day with Sipser
chapters 0–3 before our first session.