So far we have asked "which machine accepts this language?". From now on we ask a sharper question: can this problem be solved by an algorithm at all? For example: given a DFA, is its language empty? Given two DFAs, do they accept the same language? Given a program and an input, does the program ever stop?
To answer such questions precisely we need to say exactly what "solved by an algorithm" means. The Church–Turing thesis (see Variants of Turing Machines) tells us that algorithm = Turing machine. But there is a subtlety: a TM might answer "yes" reliably but, on "no" instances, run forever without ever answering. That gives two levels of solvability, and two classes of languages.
A language L is recursive (decidable) if some Turing machine accepts L and halts on every input. L is recursively enumerable, RE (semi-decidable, Turing-recognizable), if some Turing machine accepts L, where on inputs not in L it may either reject or run forever.
In this chapter we define these classes carefully, show that many natural problems about automata and grammars are decidable (with algorithms you could code today), prove the closure properties of both classes, prove the key theorem that L is recursive if and only if both L and its complement are RE, and see by a counting argument that some languages are not even RE. The DFA-equivalence decider in this chapter was run in Python on the examples shown.
Problems as Languages
A decision problem is a question with a yes/no answer for each instance. We turn it into a language by encoding each instance as a string and collecting the "yes" instances. For any object O (a DFA, a grammar, a TM, a number), ⟨O⟩ denotes its encoding as a string, and ⟨O1, O2⟩ encodes a pair. For TMs, one such encoding was given in Variants of Turing Machines.
Problem | Language |
|---|---|
Does DFA D accept w? | ADFA = { ⟨D, w⟩ : D accepts w } |
Is L(D) empty? | EDFA = { ⟨D⟩ : L(D) = ∅ } |
Do D1 and D2 accept the same language? | EQDFA = { ⟨D1, D2⟩ : L(D1) = L(D2) } |
Does CFG G generate w? | ACFG = { ⟨G, w⟩ : w ∈ L(G) } |
Does TM M accept w? | ATM = { ⟨M, w⟩ : M accepts w } |
"The problem is decidable" means exactly "its language is recursive". A decider is expected to reject strings that are not valid encodings at all; checking the format is always easy, so we ignore it from here on.
Deciders and Recognizers
Recall from Turing Machines that on an input w a TM M either accepts, rejects (halts without accepting), or loops forever.
Input | Decider (for a recursive L) | Recognizer (for an RE L) |
|---|---|---|
w ∈ L | halts and accepts | halts and accepts |
w ∉ L | halts and rejects | rejects or loops forever |
A decider always gives an answer; a recognizer only guarantees an answer for "yes". Watching a recognizer that has run for a long time tells you nothing: it may accept in the next step, or never.
Every recursive language is RE (a decider is a special recognizer). The converse is false; in Halting Problem & Undecidability we will see ATM is RE but not recursive.
Name used here | Other names you will meet |
|---|---|
Recursive language | decidable, Turing-decidable, total TM language, solvable problem |
Recursively enumerable (RE) language | semi-decidable, Turing-recognizable, partially decidable, Type 0 language |
Non-recursive language | undecidable, unsolvable problem |
Careful: "undecidable" means "not recursive"; an undecidable language may still be RE.
Decidable Problems About Automata and Grammars
Here is the good news: almost every natural question about finite automata, and several about CFGs, is decidable. Each algorithm below always halts.
ADFA: does DFA D accept w?
Simulate D on w for |w| steps and look at the final state. A DFA cannot loop: it reads one symbol per step and stops at the end of the input. Decidable.
ANFA and AREX
Convert the NFA to a DFA by subset construction (or the regular expression to an ε-NFA and then to a DFA) and use the decider for ADFA. Both conversions always finish. Decidable. This is a typical pattern: a decider may call other deciders as subroutines.
EDFA: is L(D) = ∅?
L(D) is non-empty exactly when some final state is reachable from the start state. Mark the start state, repeatedly mark every state with an arrow from a marked state, and stop when nothing new is marked (at most |Q| rounds). Accept (L is empty) if no final state is marked. Decidable.
EQDFA: is L(D1) = L(D2)?
The languages differ exactly when the symmetric difference (L1 ∩ L̄2) ∪ (L̄1 ∩ L2) is non-empty. Regular languages are closed under all these operations, so build a DFA for it (the product construction) and test emptiness. In code, we explore reachable pairs (p, q) of states and look for a pair where exactly one is final:
from collections import deque
def equivalent(D1, D2, alphabet):
"""Decide L(D1) == L(D2). Each DFA = (start, finals, delta) with delta[(q, a)] = p.
Returns (True, None) or (False, shortest string accepted by exactly one DFA)."""
s1, F1, d1 = D1
s2, F2, d2 = D2
start = (s1, s2)
parent = {start: None}
queue = deque([start])
while queue: # BFS over reachable state pairs
p, q = queue.popleft()
if (p in F1) != (q in F2): # one accepts, the other rejects
w, node = [], (p, q)
while parent[node] is not None:
node, a = parent[node]
w.append(a)
return False, ''.join(reversed(w))
for a in alphabet:
nxt = (d1[(p, a)], d2[(q, a)])
if nxt not in parent:
parent[nxt] = ((p, q), a)
queue.append(nxt)
return True, None # finitely many pairs: always halts
# D1: even number of a's (2 states)
D1 = ('E', {'E'}, {('E','a'):'O', ('O','a'):'E', ('E','b'):'E', ('O','b'):'O'})
# D2: counts a's mod 4, accepts counts 0 and 2 (a bigger DFA, same language)
D2 = (0, {0, 2}, {(0,'a'):1, (1,'a'):2, (2,'a'):3, (3,'a'):0,
(0,'b'):0, (1,'b'):1, (2,'b'):2, (3,'b'):3})
# D3: meant to be 'even number of a's', but has a bug in the move (2, b)
D3 = (0, {0, 2}, {(0,'a'):1, (1,'a'):2, (2,'a'):1, (0,'b'):0, (1,'b'):1, (2,'b'):1})
print(equivalent(D1, D2, 'ab'))
print(equivalent(D1, D3, 'ab'))Output:
(True, None)
(False, 'aab')D3 wrongly goes from state 2 (even) to state 1 (odd) on b, so it rejects aab, which has two a's; aab is the shortest string on which the two machines disagree. The loop always terminates because there are at most |Q1| × |Q2| pairs. Decidable. (Another method: minimise both DFAs and compare, using the uniqueness of the minimal DFA from DFA Minimization.)
ACFG: does CFG G generate w?
Convert G to Chomsky normal form and run the CYK Algorithm. Decidable. A naive alternative: in CNF a derivation of a non-empty w has exactly 2|w| − 1 steps, so try all derivations of that length.
Trying derivations without CNF would be a mistake: a general grammar can have arbitrarily long derivations (unit cycles, ε-rules) and the search might never end.
ECFG: is L(G) = ∅?
Mark generating variables bottom-up (see Closure & Decision Properties of CFLs) and check whether S gets marked. Decidable.
Consequence: every CFL is recursive
For a fixed CFL L with grammar G, the TM "on input w, run CYK for G on w" halts on every input and accepts exactly L. So
Regular ⊂ CFL ⊂ CSL ⊂ Recursive ⊆ RE(CSL ⊂ Recursive was shown in Chomsky Hierarchy & Linear Bounded Automata. Whether the last ⊆ is proper is settled in the next chapter.)
Not everything about CFGs is decidable, though: EQCFG (are two CFGs equivalent?) and "does G generate all of Σ*?" are undecidable. Why does the EQDFA trick fail for CFGs? Because it needs complement and intersection, under which CFLs are not closed.
Closure Properties of Recursive Languages
Let M1 and M2 be deciders for L1 and L2. Because they always halt, we can run them one after the other.
Operation | Decider for the result, on input w |
|---|---|
Complement L̄1 | Run M1; accept if it rejects, reject if it accepts. (Swap the answers.) |
Union L1 ∪ L2 | Run M1, then M2; accept if either accepted. |
Intersection L1 ∩ L2 | Run M1, then M2; accept if both accepted. |
Difference L1 − L2 | = L1 ∩ L̄2 |
Concatenation L1L2 | For each of the |w| + 1 ways to split w = xy, run M1 on x and M2 on y; accept if some split works. |
Kleene star L1* | Accept if w = ε; otherwise try each of the 2|w|−1 ways to cut w into non-empty pieces and check every piece with M1. Finitely many cuts, so it halts. |
Reversal L1R | Reverse w, run M1. |
Inverse homomorphism h−1(L1) | Compute h(w), run M1. |
Not closed under (arbitrary) homomorphism. To decide whether w ∈ h(L) we would have to search for some x ∈ L with h(x) = w. If h erases symbols, there are infinitely many candidates x, and the search may never end. In fact every RE language is an erasing homomorphic image of some recursive language. (For ε-free homomorphisms, |x| ≤ |w|, so the search is finite and recursive languages are closed.)
Closure Properties of RE Languages
Now M1 and M2 are only recognizers: they may run forever on strings not in their languages. This changes the constructions.
Union needs parallel simulation
The naive approach "run M1 on w; if it rejects, run M2" fails. Suppose w ∉ L1 but w ∈ L2, and M1 loops on w. Then we never get to start M2, and we wrongly fail to accept w.
Instead, run them in parallel, one step at a time (for example, on a 2-tape TM, or alternating steps on one tape):
On input w:
for k = 1, 2, 3, ...:
run step k of M1 on w if M1 has accepted, ACCEPT
run step k of M2 on w if M2 has accepted, ACCEPT
(if both have halted and rejected, REJECT)If w ∈ L1 ∪ L2, one of them accepts after some finite number of steps, and the parallel run reaches that step. So RE is closed under union.
The other operations
Intersection: run M1 on w; if it accepts, run M2 on w; accept if both accept. Sequential is fine here: if w is in both, both runs finish. If either loops, w is not in the intersection anyway.
Concatenation: there are |w| + 1 splits; for each split we need M1(x) and M2(y) to accept. Run all splits in parallel (or use a nondeterministic TM that guesses the split). Closed.
Kleene star: guess the cutting of w nondeterministically, check each piece. Closed.
Homomorphism: guess x with h(x) = w and check x ∈ L1; a nondeterministic TM (or dovetailing over all x and all step counts) does it. Closed, even for erasing h.
Reversal, inverse homomorphism, intersection with regular: closed, as for recursive languages.
Complement: NOT closed. Swapping answers fails because a recognizer may never give a "reject" answer to swap. The next chapter shows a concrete RE language whose complement is not RE.
Side by side
Operation | Recursive | RE |
|---|---|---|
Union | Yes | Yes (parallel simulation) |
Intersection | Yes | Yes |
Complement | Yes | No |
Difference | Yes | No (but RE − recursive is RE) |
Concatenation, Kleene star | Yes | Yes |
Reversal, inverse homomorphism | Yes | Yes |
Homomorphism (arbitrary) | No | Yes |
The Complement Theorem
Theorem: L is recursive if and only if both L and its complement L̄ are recursively enumerable.
(⇒) If L is recursive, so is L̄ (swap answers). Every recursive language is RE. So both are RE.
(⇐) Let M1 recognise L and M2 recognise L̄. Build M:
M on input w:
run M1 and M2 on w in parallel, one step each at a time
if M1 accepts: ACCEPT
if M2 accepts: REJECTEvery w is in exactly one of L and L̄, so exactly one of M1, M2 eventually accepts. Hence M always halts, and it accepts exactly L. So L is recursive.
Intuitively: a recognizer for L gives certified "yes" answers, a recognizer for L̄ gives certified "no" answers, and together they give a decider.
The four boxes
For any language L, exactly one of these cases holds:
L | L̄ | Possible? | Example |
|---|---|---|---|
Recursive | Recursive | Yes | ADFA, any CFL, any CSL |
RE, not recursive | not RE | Yes | L = ATM (next chapter) |
not RE | RE, not recursive | Yes | L = complement of ATM |
not RE | not RE | Yes | { ⟨M⟩ : L(M) = Σ* } (see Reductions & Rice's Theorem) |
Recursive | not recursive | Impossible | recursive languages are closed under complement |
RE, not recursive | RE | Impossible | by the complement theorem L would be recursive |
A very common exam shortcut: if L is RE but not recursive, then L̄ is not RE.
Why "Recursively Enumerable"? Enumerators Again
In Variants of Turing Machines we saw that L is RE exactly when some enumerator (a TM with a printer) prints all strings of L, in some order, possibly with repeats. Recursive languages have a nice enumerator characterisation too. Use shortlex (canonical) order: shorter strings first, strings of the same length in dictionary order: ε, 0, 1, 00, 01, 10, 11, 000, ....
An infinite language L is recursive if and only if some enumerator prints exactly the strings of L in increasing shortlex order. (Finite languages are regular, hence recursive.)
(⇒) With a decider M: for each string s in shortlex order, run M on s (it halts) and print s if accepted. The output is in order.
(⇐) To decide w: run the enumerator until it prints w (accept) or prints some string that comes after w in shortlex order (reject; since output is increasing, w will never appear). Because L is infinite, one of these happens after finitely many steps.
So the difference between RE and recursive is the difference between "listable in some order" and "listable in order", which is exactly what lets you stop searching.
Not Every Language Is RE: A Counting Argument
Before seeing a specific non-RE language, here is a short argument that most languages are not RE.
There are countably many TMs. Every TM has an encoding as a finite binary string, and the finite binary strings can be listed: ε, 0, 1, 00, 01, .... So TMs can be listed M1, M2, M3, ..., and so can the RE languages L(M1), L(M2), ....
There are uncountably many languages over {0, 1}. List all strings w1 = ε, w2 = 0, w3 = 1, w4 = 00, .... A language is the same as an infinite 0/1 sequence (1 at position i if wi is in it). Given any list of languages, build a new one by flipping the diagonal:
w1=ε w2=0 w3=1 w4=00 ...
L1 1 0 0 1
L2 0 0 1 1
L3 1 1 1 0
L4 0 1 0 0
...
diagonal: 1 0 1 0 ...
flipped D: 0 1 0 1 ... D differs from every Li at wiD differs from Li on string wi, so D is not in the list. No list can contain all languages (Cantor's diagonal argument).
Countably many recognizers but uncountably many languages: some languages (in fact, almost all) are not RE. This proof does not name one. A concrete non-RE language, the diagonal language Ld = { ⟨M⟩ : M does not accept ⟨M⟩ }, is obtained by applying the same diagonal trick to the list of TMs; that is done in Halting Problem & Undecidability.
The Big Picture
┌──────────────────────────────────────────────────────────────┐
│ All languages (uncountably many) e.g. L_d │
│ ┌────────────────────────────────────────────────────────┐ │
│ │ RE (semi-decidable): a TM says "yes" when the answer │ │
│ │ is yes e.g. A_TM │ │
│ │ ┌──────────────────────────────────────────────────┐ │ │
│ │ │ Recursive (decidable): a TM always halts │ │ │
│ │ │ A_DFA, E_DFA, EQ_DFA, A_CFG, E_CFG, │ │ │
│ │ │ every CSL, every CFL, every regular language │ │ │
│ │ └──────────────────────────────────────────────────┘ │ │
│ └────────────────────────────────────────────────────────┘ │
└──────────────────────────────────────────────────────────────┘Common Mistakes
"A TM accepts L, so L is decidable." Only if the TM halts on every input. Accepting L only makes L RE.
Running recognizers one after the other. For union (and for the complement theorem) the first one might loop. Interleave their steps.
"Undecidable means no TM accepts it." No: undecidable (non-recursive) languages like ATM are still RE.
"Every subset of a decidable language is decidable." False: every language over Σ is a subset of the decidable language Σ*.
Thinking "decidable" is about one instance. Decidability is about a whole infinite family of instances. Any single yes/no question (say, "does this particular TM halt on this particular input?") is trivially decidable: one of the two machines "always accept" or "always reject" answers it correctly, even if we do not know which.
Mixing up the directions of the complement theorem. L recursive ⇔ L and L̄ both RE. Not "L RE ⇒ L̄ RE".
Practice and GATE-Style Questions
Q1. L1 is recursive and L2 is RE but not recursive. Which of the following are necessarily RE: (a) L1 ∪ L2 (b) L1 ∩ L2 (c) L̄2 (d) L2 − L1 (e) L1 − L2?
(a) RE (L1 is also RE). (b) RE. (c) Not RE: if it were, L2 would be recursive by the complement theorem. (d) L2 ∩ L̄1, where L̄1 is recursive, hence RE: RE. (e) L1 ∩ L̄2: not necessarily RE. Take L1 = Σ*; then it is L̄2, which is not RE.
Q2. Both L and L̄ are recursively enumerable. What can you conclude?
L is recursive (and so is L̄). Run both recognizers in parallel; exactly one accepts.
Q3. Which of these problems are decidable: (a) EDFA (b) EQDFA (c) ACFG (d) ECFG (e) EQCFG?
(a) to (d) are decidable (reachability, product + emptiness, CYK, generating symbols). (e) is undecidable.
Q4. Why does the decider for L1* (L1 recursive) halt, and why would the same construction not prove that RE languages are closed under star by running pieces one at a time?
For a recursive L1, each check of a piece halts, and there are only 2|w|−1 ways to cut w, so the whole search halts. For an RE L1, checking one piece may loop forever, blocking all other cuts. RE languages are closed under star, but the proof must check all cuts in parallel or guess the cut nondeterministically.
Q5. Is the set of all TMs countable? Is the set of all languages over {a}?
TMs: countable (each has a finite binary encoding). Languages over {a}: uncountable. They correspond to subsets of {ε, a, aa, ...}, i.e. to infinite 0/1 sequences. So even over a one-letter alphabet, some languages are not RE.
Q6. A recognizer M for L has been simulated on w for 106 steps without halting. Someone also has a recognizer M' for L̄, which has not accepted w in 106 steps either. What do you know?
Nothing yet about w, but you do know L is recursive, and the parallel simulation of M and M' is guaranteed to finish eventually on w with the correct answer.
Q7. Interview: why is ADFA decidable while ATM (asked in the next chapter) is not, when both just ask "does the machine accept w"?
A DFA always halts after exactly |w| steps, so simulation is a decider. A TM can run forever, and simulation alone cannot tell "has not halted yet" from "will never halt". The next chapter proves that no cleverer method can work either.
Summary
Recursive (decidable): some TM accepts L and halts on every input. RE (semi-decidable): some TM accepts L, possibly looping on strings not in L.
Regular ⊂ CFL ⊂ CSL ⊂ Recursive ⊆ RE (the last inclusion is proper: next chapter).
Decidable: ADFA, ANFA, AREX, EDFA, EQDFA, ACFG, ECFG. Undecidable: EQCFG.
Recursive languages are closed under union, intersection, complement, difference, concatenation, star, reversal and inverse homomorphism, but not arbitrary homomorphism.
RE languages are closed under union (by parallel simulation), intersection, concatenation, star, homomorphism, but not complement.
L is recursive ⇔ L and L̄ are both RE. So if L is RE but not recursive, L̄ is not RE.
L is RE ⇔ some enumerator lists it; an infinite L is recursive ⇔ some enumerator lists it in shortlex order.
TMs are countable and languages are uncountable, so non-RE languages exist.
A decider always answers; a recognizer only promises to say "yes". Two recognizers, one for "yes" and one for "no", run side by side make a decider, and that single idea organises everything about recursive and recursively enumerable languages.