13 Decidable & Recognizable Languages

Why Decidability?

In the Turing machines chapter, we introduced the most powerful model of computation — and immediately found a catch. TMs can loop forever, creating two distinct classes: recognizable languages (a TM accepts all members, but may loop on non-members) and decidable languages (a TM always halts with the right answer). That was an abstract distinction.

Now we make it concrete. We're going to ask a very specific kind of question: can we build a TM that answers questions about other machines? Given a DFA and a string, can we determine whether the DFA accepts that string? Given a CFG, can we test whether its language is empty? Given two DFAs, can we check whether they recognize the same language?

These are languages about machines — the inputs are encoded descriptions of automata, grammars, or TMs, and the question is: can a TM always give the right answer? For simple models (DFAs, NFAs, regex), the answer is almost always "yes." For CFGs, cracks start to appear. For TMs themselves, things fall apart entirely — which is the subject of the next page.

The meta-level shift. Until now, machines processed strings — sequences of symbols like $0011$ or $aabbb$. Now, machines process descriptions of other machines. We encode a DFA as a string $\langle B \rangle$, a CFG as a string $\langle G \rangle$, a TM as a string $\langle M \rangle$. A TM that "decides $A_{\text{DFA}}$" is a program that takes another program as input and analyzes it. This is the jump from "computing" to "computing about computation."

Languages About Machines

We define four standard questions about any computational model. Each question becomes a language — a set of encodings that satisfy the property:

Problem	Name	Language	Question
Acceptance	$A_X$	$\{\langle M, w \rangle \mid M \text{ is an } X \text{ and } M \text{ accepts } w\}$	Does machine $M$ accept string $w$?
Emptiness	$E_X$	$\{\langle M \rangle \mid M \text{ is an } X \text{ and } L(M) = \emptyset\}$	Does $M$ accept nothing at all?
Universality	$ALL_X$	$\{\langle M \rangle \mid M \text{ is an } X \text{ and } L(M) = \Sigma^*\}$	Does $M$ accept every string?
Equivalence	$EQ_X$	$\{\langle M_1, M_2 \rangle \mid M_1, M_2 \text{ are } X\text{s and } L(M_1) = L(M_2)\}$	Do $M_1$ and $M_2$ recognize the same language?

Here $X$ stands for the model: DFA, NFA, RegEx, CFG, PDA, or TM. The question is: for which combinations is the language decidable?

$A_{\text{DFA}}$ is Decidable

Start with the simplest case. Given a DFA $B$ and a string $w$, can we always determine whether $B$ accepts $w$?

Theorem (Sipser 4.1). $A_{\text{DFA}} = \{\langle B, w \rangle \mid B \text{ is a DFA and } B \text{ accepts } w\}$ is decidable.

Proof — constructing a decider $M$

$M = $ "On input $\langle B, w \rangle$ where $B$ is a DFA and $w$ is a string:

Simulate $B$ on input $w$ — walk through $w$ symbol by symbol, tracking the current state of $B$ using its transition function $\delta$.
If the simulation ends in an accept state of $B$, accept. If it ends in a non-accept state, reject."

Why this is a decider: DFAs always halt — they read $|w|$ symbols and stop. So the simulation always terminates. $M$ never loops, and it gives the correct answer. Therefore $A_{\text{DFA}}$ is decidable.

This is the template for all decidability proofs: build a TM, describe its algorithm, argue it always halts, argue it gives the right answer.

$A_{\text{NFA}}$ and $A_{\text{CFG}}$ are Decidable

What about NFAs? We could try simulating all nondeterministic branches, but there's a much cleaner approach: reduce to the solved problem.

Theorem (Sipser 4.2). $A_{\text{NFA}} = \{\langle B, w \rangle \mid B \text{ is an NFA and } B \text{ accepts } w\}$ is decidable.

Proof — reduce NFA to DFA

$N = $ "On input $\langle B, w \rangle$ where $B$ is an NFA and $w$ is a string:

Convert $B$ to an equivalent DFA $C$ using the subset construction.
Run the decider $M$ for $A_{\text{DFA}}$ on input $\langle C, w \rangle$.
If $M$ accepts, accept. If $M$ rejects, reject."

Both steps always terminate: subset construction is a finite procedure, and $M$ is a decider. Since NFA-to-DFA conversion preserves the language, this is correct.

Similarly for regular expressions: convert to NFA first, then to DFA, then simulate. $A_{\text{RegEx}}$ is decidable.

Theorem (Sipser 4.7). $A_{\text{CFG}} = \{\langle G, w \rangle \mid G \text{ is a CFG and } G \text{ generates } w\}$ is decidable.

Proof — convert to CNF and enumerate derivations

$S = $ "On input $\langle G, w \rangle$ where $G$ is a CFG and $w$ is a string:

Convert $G$ to Chomsky Normal Form (CNF).
List all derivations of exactly $2|w| - 1$ steps (in CNF, any string of length $n$ requires exactly $2n - 1$ derivation steps). If $w = \varepsilon$, check whether the start variable has a rule $S \to \varepsilon$.
If any derivation generates $w$, accept. If none does, reject."

Why this halts: The key insight is that CNF limits the number of derivation steps to exactly $2|w| - 1$. There are finitely many derivations of that length, so we check them all and stop. Without CNF, we'd have no bound — derivations could get arbitrarily long via unit productions and $\varepsilon$-rules, making the search infinite.

Why not just "simulate the PDA"? A PDA is nondeterministic and might loop on some branches (revisiting the same configuration forever). Unlike NFAs, where each path is finite (bounded by input length), a PDA can push and pop indefinitely without consuming input. The CNF approach avoids this entirely by bounding the search space.

$E_{\text{DFA}}$ and $EQ_{\text{DFA}}$ are Decidable

Emptiness asks: does a machine accept any string at all? For DFAs, this reduces to a graph reachability question.

Theorem (Sipser 4.4). $E_{\text{DFA}} = \{\langle A \rangle \mid A \text{ is a DFA and } L(A) = \emptyset\}$ is decidable.

Proof — reachability check

$T = $ "On input $\langle A \rangle$ where $A$ is a DFA:

Mark the start state.
Repeat: mark any unmarked state that has a transition from an already-marked state.
If no accept state is marked, accept (the language is empty). If some accept state is marked, reject (the language is not empty)."

This is just BFS/DFS on the state graph. It terminates because the state set is finite. A DFA accepts at least one string iff some accept state is reachable from the start state.

For NFAs: convert to DFA first (or run the same reachability on the NFA graph — reachability works on nondeterministic graphs too). For CFGs: the emptiness test removes useless variables and checks whether the start variable generates anything.

Theorem (Sipser 4.5). $EQ_{\text{DFA}} = \{\langle A, B \rangle \mid A, B \text{ are DFAs and } L(A) = L(B)\}$ is decidable.

Proof — symmetric difference

Two languages are equal iff their symmetric difference is empty:

$$L(A) = L(B) \iff (L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B)) = \emptyset$$

$F = $ "On input $\langle A, B \rangle$:

Construct a DFA $C$ that recognizes the symmetric difference of $L(A)$ and $L(B)$. (Use product construction for intersection and complement.)
Run the decider for $E_{\text{DFA}}$ on $\langle C \rangle$.
If the emptiness test accepts (symmetric difference is empty), accept. Otherwise, reject."

Each step terminates and uses only decidable operations on DFAs. This is a beautiful example of combining closure properties with decidability results.

$ALL_X$ — Universality: Does It Accept Everything?

$ALL_X = \{\langle M \rangle \mid M \text{ is an } X \text{ and } L(M) = \Sigma^*\}$. The question: does this machine accept every possible string? Not just some, not just many — literally all of them.

This is the opposite of emptiness. $E_X$ asks "does it accept nothing?" $ALL_X$ asks "does it accept everything?" And the strategy for solving it is to flip one into the other using complement.

$ALL_{\text{DFA}}$ is decidable. The trick: $L(A) = \Sigma^*$ iff $\overline{L(A)} = \emptyset$. So complement the DFA (swap accept/non-accept states — one step, always works), then run $E_{\text{DFA}}$ on the complement. If the complement is empty, the original accepts everything.

This works because DFAs are closed under complement — flipping accept states gives you a valid DFA for the complement language. The same applies to NFAs and regex (convert to DFA first, then complement).

$ALL_{\text{CFG}}$ is undecidable. You'd want the same strategy: complement the CFG, then check emptiness. But CFLs are NOT closed under complement. There is no algorithm to build a CFG for $\overline{L(G)}$ from a CFG for $L(G)$. The strategy collapses at step one.

And it's not just that this particular strategy fails — no strategy works. $ALL_{\text{CFG}}$ is provably undecidable (via reduction from the halting problem, covered in undecidability).

CFG: Where Cracks Appear

For DFAs, NFAs, and regex, all four problems (A, E, ALL, EQ) are decidable. This makes sense — regular languages are simple enough that we can always answer questions about them. CFGs are trickier.

Decidable for CFGs:

$A_{\text{CFG}}$ — decidable (CNF + bounded derivation search)
$E_{\text{CFG}}$ — decidable (remove useless variables, check if start variable generates anything)

Undecidable for CFGs:

$ALL_{\text{CFG}}$ — undecidable. The complement trick fails (CFLs not closed under complement), and no alternative strategy exists. See section above.
$EQ_{\text{CFG}}$ — undecidable. Proven by reduction from $ALL_{\text{CFG}}$: if we could decide $EQ_{\text{CFG}}$, we could decide $ALL_{\text{CFG}}$ by comparing $G$ with a grammar that generates $\Sigma^*$.

Proof sketch — $EQ_{\text{CFG}}$ is undecidable (reduction from $ALL_{\text{CFG}}$)

Assume for contradiction that some TM $M$ decides $EQ_{\text{CFG}}$. We build a decider $D$ for $ALL_{\text{CFG}}$:

$D = $ "On input $\langle G \rangle$ where $G$ is a CFG:

Construct $G' = (\{A\}, \Sigma, R, A)$ where $R$ has rules $A \to AA$, $A \to \varepsilon$, and $A \to x$ for every $x \in \Sigma$. Then $L(G') = \Sigma^*$.
Run $M$ on $\langle G, G' \rangle$.
If $M$ accepts, accept. If $M$ rejects, reject."

$D$ decides $ALL_{\text{CFG}}$. But $ALL_{\text{CFG}}$ is undecidable — contradiction. So $M$ cannot exist.

The Decidability Table

This table is one of the central results of the course. It summarizes which problems are decidable for which models. Study the pattern: as the model gets more powerful, decidability breaks down.

	DFA	NFA	RegEx	CFG	PDA	TM
$A$	Yes	Yes	Yes	Yes	Yes	?
$E$	Yes	Yes	Yes	Yes	Yes	?
$ALL$	Yes	Yes	Yes	No	No	?
$EQ$	Yes	Yes	Yes	No	No	?

Reading the table. The first three columns (DFA, NFA, RegEx) are identical — all "Yes." This makes sense: NFA and RegEx can always be converted to DFA, so any DFA algorithm works for them too. The vertical line between RegEx and CFG is where things break: $ALL$ and $EQ$ become undecidable. The PDA column mirrors CFG (since CFG = PDA in power). The TM column has question marks — those are all undecidable, proven in the next page.

Why $ALL_{\text{DFA}}$ and $EQ_{\text{DFA}}$ are decidable — the closure property trick:

$ALL_{\text{DFA}}$: Complement the DFA (swap accept/non-accept states), then check if the complement's language is empty using the $E_{\text{DFA}}$ algorithm. $L(A) = \Sigma^*$ iff $L(\overline{A}) = \emptyset$. This works because DFAs are closed under complement.
$EQ_{\text{DFA}}$: Build the symmetric difference $(L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B))$ as a DFA, then check emptiness. This works because DFAs are closed under complement, intersection, and union.

Why this breaks for CFGs: CFLs are NOT closed under complement or intersection. You can't complement a CFG and check emptiness. The structural tricks that make DFAs analyzable simply don't apply to CFGs — and that's exactly where decidability breaks down.

Why are NFA/RegEx/PDA columns "free"?

NFA/RegEx: Convert to DFA first, then use the DFA algorithm. This always works because the conversion is mechanical and finite.
PDA: For acceptance and emptiness, use the CFG algorithm (since every PDA has an equivalent CFG). For $ALL$ and $EQ$, the problems are undecidable for the same reason as CFGs — the conversion doesn't help when the underlying problem is impossible.

Enumerators

An enumerator is a TM with a "printer" — instead of accepting or rejecting, it prints strings one at a time. The language enumerated by $E$ is the set of all strings it ever prints (in any order, possibly with repetitions). It may run forever, printing infinitely many strings.

Theorem 3.21 (Sipser). A language is Turing-recognizable if and only if some enumerator enumerates it.

Proof sketch — both directions

Enumerator $\Rightarrow$ Recognizer: Given an enumerator $E$ for language $L$, build a TM $M$ that on input $w$: run $E$, and every time $E$ prints a string, compare it to $w$. If they match, accept. If $w \in L$, the enumerator will eventually print it, so $M$ accepts. If $w \notin L$, $M$ runs forever (never finds a match).

Recognizer $\Rightarrow$ Enumerator: Given a recognizer $M$ for $L$, build an enumerator $E$: for $i = 1, 2, 3, \ldots$: run $M$ for $i$ steps on each of the strings $s_1, s_2, \ldots, s_i$ (where $s_j$ is the $j$-th string in lexicographic order). If $M$ accepts $s_j$ within $i$ steps, print $s_j$.

The key trick in the second direction: we interleave (or dovetail) computations rather than running them sequentially. If we ran $M$ on $s_1$ to completion before starting $s_2$, we'd get stuck on the first string that causes $M$ to loop. The interleaving ensures every string gets its turn. This dovetailing technique appears throughout computability theory — any time you need to search an infinite space without getting stuck on a single looping computation.

Enumerable in lexicographic order $\iff$ decidable. If you can enumerate a language in order (never printing a "smaller" string after a "larger" one), the language is decidable. To decide whether $w \in L$: run the enumerator until it either prints $w$ (accept) or prints something past $w$ in order (reject — $w$ was skipped, so it's not in $L$). This always halts because strings keep getting "bigger."

Conversely, if the language is decidable: enumerate $\Sigma^*$ in lexicographic order, test each string with the decider, print it if accepted. This produces the language in order.

Recognizable vs. Decidable — The Full Picture

We now have enough machinery to state the key relationships precisely:

The language hierarchy for computability:

Decidable $\subset$ Recognizable $\subset$ All Languages
Every decidable language is recognizable (a decider is a recognizer that always halts)
Not every recognizable language is decidable ($A_{\text{TM}}$ — see next page)
Not every language is recognizable (there are "more" languages than TMs — a cardinality argument)

Theorem (Sipser 4.22). A language is decidable if and only if both it and its complement are Turing-recognizable. $$L \text{ is decidable} \iff L \text{ is recognizable AND } \overline{L} \text{ is recognizable}$$

Proof — run both recognizers in parallel

($\Rightarrow$): If $L$ is decidable, it's recognizable. And a decider for $L$ can be converted into a decider for $\overline{L}$ (flip accept/reject), so $\overline{L}$ is also recognizable.

($\Leftarrow$): Given recognizer $M_1$ for $L$ and recognizer $M_2$ for $\overline{L}$, build a decider: on input $w$, run $M_1$ and $M_2$ in parallel (alternating one step of each). Every string $w$ is either in $L$ or in $\overline{L}$, so one of the two recognizers must eventually accept. When one accepts, we know the answer: if $M_1$ accepts, then $w \in L$ (accept); if $M_2$ accepts, then $w \in \overline{L}$ (reject).

This always halts because one recognizer is guaranteed to accept. The parallel execution prevents us from getting stuck waiting on a recognizer that loops.

Why this theorem matters. It gives us a new tool for proving things are not decidable and not recognizable:

If $L$ is recognizable but $\overline{L}$ is NOT recognizable, then $L$ is undecidable (because decidable requires both)
A language is called co-Turing-recognizable (or co-r.e.) if its complement is Turing-recognizable
If a language is undecidable and co-recognizable, then it must be unrecognizable (contrapositive of the theorem)

This is exactly how the lectures show that $ALL_{\text{CFG}}$ is not just undecidable but unrecognizable: it's co-recognizable (you can enumerate counterexamples) but undecidable, so it can't be recognizable.

Exercises

Exercise 1: Building Deciders

Give a high-level description of a decider for $E_{\text{CFG}} = \{\langle G \rangle \mid G \text{ is a CFG and } L(G) = \emptyset\}$.

Hint: Think about which variables can generate strings of terminals. A grammar's language is non-empty iff the start variable can eventually produce a terminal string.

Exercise 2: The Complement Connection

We know $ALL_{\text{CFG}}$ is undecidable. A TM can enumerate all strings $w \in \Sigma^*$, test each against the CFG (using the decider for $A_{\text{CFG}}$), and reject when it finds a string not generated by $G$. What does this tell us about the recognizability of $ALL_{\text{CFG}}$?

Exercise 3: Why Not Simulate the TM?

Someone proposes: "To decide $A_{\text{TM}}$, just simulate the TM on the input string. If it accepts, accept. If it rejects, reject." What's wrong with this argument?

Summary

Decidability — the essentials:

Languages about machines: $A, E, ALL, EQ$ — four standard questions asked about each model (DFA, NFA, RegEx, CFG, PDA, TM)
Regular models: All four problems are decidable. NFA and RegEx reduce to DFA.
Context-free models: $A$ and $E$ are decidable. $ALL$ and $EQ$ are undecidable.
Turing machines: $A_{\text{TM}}$ is recognizable but not decidable. The TM column is all question marks (resolved in the next page).
Proof template: Build a TM, describe algorithm, prove it always halts, prove correctness
Reduction technique: "If I could decide problem X, I could decide problem Y" — used for both decidability (positive reductions) and undecidability (contradiction)
Enumerators: A language is recognizable iff enumerable. Enumerable in order iff decidable.
Key theorem: $L$ is decidable $\iff$ both $L$ and $\overline{L}$ are recognizable
Co-recognizable: $L$ is co-recognizable if $\overline{L}$ is recognizable. If $L$ is undecidable and co-recognizable, then $L$ is not recognizable.

← Turing Machines Index Undecidability →

Problem	Name	Language	Question
Acceptance	\(A_X\)	\(\{\langle M, w \rangle \mid M \text{ is an } X \text{ and } M \text{ accepts } w\}\)	Does machine \(M\) accept string \(w\)?
Emptiness	\(E_X\)	\(\{\langle M \rangle \mid M \text{ is an } X \text{ and } L(M) = \emptyset\}\)	Does \(M\) accept nothing at all?
Universality	\(ALL_X\)	\(\{\langle M \rangle \mid M \text{ is an } X \text{ and } L(M) = \Sigma^*\}\)	Does \(M\) accept every string?
Equivalence	\(EQ_X\)	\(\{\langle M_1, M_2 \rangle \mid M_1, M_2 \text{ are } X\text{s and } L(M_1) = L(M_2)\}\)	Do \(M_1\) and \(M_2\) recognize the same language?

	DFA	NFA	RegEx	CFG	PDA	TM
\(A\)	Yes	Yes	Yes	Yes	Yes	?
\(E\)	Yes	Yes	Yes	Yes	Yes	?
\(ALL\)	Yes	Yes	Yes	No	No	?
\(EQ\)	Yes	Yes	Yes	No	No	?