Every "natural question" about a DFA or a CFG can be answered by an algorithm.
BCS 402 · Dr. Arash Kermani · CUD
🎧 Narration
1 · Why this module exists
By this point in the course you can already tell a DFA and a CFG apart, and you can simulate
them in your head. This module is about a different question: given the description of a
DFA or a CFG, can a computer answer questions about it — like "does this DFA accept this
string?" or "is the language of this grammar empty?" — by following an algorithm that is
guaranteed to halt with the right answer?
The headline result is yes, for the five questions in this module. Each one will get its own
section, but they all share a common shape, so it is worth naming it now:
🔊 Template
Decidability template. To show a language L is decidable,
describe a Turing machine that on input ⟨x⟩ always halts, and accepts
if x ∈ L, rejects otherwise. We will only ever describe it in plain
English; the formal TM is left implicit.
The five questions of this lecture
Name
Set
Plain English
ADFA
{⟨B, w⟩ : B is a DFA, w ∈ L(B)}
"Does DFA B accept string w?"
EDFA
{⟨B⟩ : L(B) = ∅}
"Is the language of DFA B empty?"
EQDFA
{⟨A, B⟩ : L(A) = L(B)}
"Do DFAs A and B accept exactly the same strings?"
ACFG
{⟨G, w⟩ : w ∈ L(G)}
"Does CFG G generate string w?"
ECFG
{⟨G⟩ : L(G) = ∅}
"Is the language of CFG G empty?"
All five are decidable. Notice what is conspicuously missing from this list:
EQCFG, the equivalence problem for context-free grammars. It is
not decidable, and we will prove that in Module 3. The line between this module
and the next is drawn exactly there.
🔊 Encodings
A word about encodings
The notation ⟨B⟩ means "the encoding of B as a string" — e.g. listing
its states, alphabet, transition function, start and accept states. The specific encoding does
not matter, as long as we can recover the DFA from it and one DFA has exactly one encoding.
Throughout the course we will mostly stop fussing about encodings; just treat
⟨·⟩ as quote marks around a machine description.
🎧 Narration
2 · ADFA: does DFA B accept string w?
The algorithm is the most natural one imaginable: just simulate the DFA on the
input. Read one character at a time, walk through the transitions, and at the end
check whether you ended in an accept state. DFAs are deterministic, so there is exactly one
walk to take; and the walk has length |w|, which is finite.
🔊 Proof sketch
Proof sketch — ADFA is decidable
Construct a TM M that on input ⟨B, w⟩:
(1) parses the DFA, (2) sets a pointer to the start state and reads w
left to right, updating the state per the transition function, (3) accepts if the final state
is in the accept set, rejects otherwise. M always halts (after exactly
|w| steps of simulation), so ADFA is decidable. ∎
ADFA is decidable because we can build a Turing machine that literally simulates the DFA. Three snapshots show the simulation in motion: at each step, the head reads the next input symbol and the tracked B-state updates via δ. After all of w is consumed, the TM accepts iff the final B-state is in F.
Try it: a DFA simulator
Below is a small DFA over the alphabet {0, 1}. The default accepts exactly those binary
strings with an even number of 1s. Type a string and step through; the active state lights up.
Click the transition table to edit the DFA.
ADFA simulator Widget 1
Input tape — read left-to-right
Step 0 / 7
Current state q0
Read so far ε
Verdict —
Transition table (click a cell to edit)
δ
0
1
Start state: q0 · Accept states (toggle):
q0 ✓q1
Step 0
Press Step to walk through the simulation one character at a time.
The simulator just walks through the DFA's transition function, exactly as the
ADFA decider would.
That is the whole proof. The widget above is the decision procedure — there is no
separate "Turing machine" to imagine; this is what one would do.
🔊 Corollaries
Corollaries (Sipser Theorems 4.2 and 4.3). The same decidability extends immediately to NFAs and regular expressions:
ANFA = {⟨N, w⟩ : N is an NFA, w ∈ L(N)} is decidable — convert N to an equivalent DFA via the subset construction (prereq §2), then call the ADFA decider.
AREX = {⟨R, w⟩ : R is a regular expression, w ∈ L(R)} is decidable — convert R to an NFA via Sipser Theorem 1.54, then call the ANFA decider.
Sipser presents these as immediate consequences in L7, since the conversions are themselves computable.
🎧 Narration
3 · EDFA: is L(B) empty?
"Empty" sounds harder than "accepts this string", but it is actually easier: emptiness
is a question about structure, not about a specific input. A DFA accepts some
string if and only if there is a path from its start state to some accept state.
🔊 Algorithm
Algorithm — graph reachability
Treat the DFA as a directed graph (states = nodes, transitions = edges). Run BFS or DFS from
the start state. If any reachable node is an accept state, output not empty;
otherwise, output empty. The DFA has finitely many states, so the search halts.
BFS expands outward from the start state. The DFA's language is empty if and only if no accept state is ever reached. Linear time in the number of states and transitions.
Try it: emptiness by reachability
Below is a DFA with 5 states. Toggle which states are accept states and click Run
reachability to mark the reachable states (shaded). The verdict appears at the bottom.
EDFA reachability walkthrough Widget 2
Frontier {q0}
Discovered {q0}
Verdict running…
Step 0
Click Step BFS to expand the next frontier of the breadth-first search from q0.
Click a state to toggle whether it is an accept state.
The procedure halts because the DFA has only finitely many states — at most |Q|
of them, where |Q| is the number of states. So the algorithm runs in
linear time in the size of the DFA, and EDFA is not just decidable
but very efficiently decidable.
🎧 Narration
4 · EQDFA: do DFAs A and B accept the same language?
This is where things get a little clever. We reduce equivalence to emptiness using the
symmetric difference:
Sipser §4.5 (Theorem 4.5): L(A) = L(B) iff their symmetric difference is empty. The symmetric difference is a Boolean combination of L(A) and L(B), and regular languages are closed under union, intersection, and complement — so a DFA C recognizing L(A) △ L(B) exists. Then EQDFA reduces to EDFA(C), which we already know how to decide. No explicit pair-state construction needed in the proof.
The symmetric difference is the set of strings on which A and
Bdisagree. They are equivalent iff they never disagree iff
the symmetric difference is empty.
Now, the regular languages are closed under union, intersection, and complement (we proved this
in Lecture 1). So there is a DFA C that recognizes
L(A) △ L(B) — we just build it. And we already know how to test
a DFA for emptiness: use EDFA from the previous section.
🔊 Algorithm
Algorithm
On input ⟨A, B⟩: (1) construct a DFA C with L(C) = L(A) △ L(B), the symmetric difference. Regular languages are closed under union, intersection, and complement, so such a C exists. A standard construction sets C's states to pairs (qA, qB) and marks the pair accepting iff exactly one of qA, qB is accepting. (2) Test L(C) = ∅ using the reachability procedure from §3. Accept iff yes.
Try it: build DFA C for the symmetric difference, one cell at a time
Below: two small DFAs A and B, and a DFA C
with L(C) = L(A) △ L(B). Click Build C to
fill in the table step by step. Cells marked exactly-one
are accept states of C; if no exactly-one state is reachable from the start pair, the
languages are equal.
🔊 Widget walkthrough
How to read the widget — step by step
1 · The two input DFAs.
A tracks the parity of 0s. State p0 (start, double-circled = accept) means "even count so far." State p1 means "odd count." A 0 toggles between them; a 1 is a self-loop. So L(A) = {strings with an even number of 0s}.
B tracks the last symbol. State r0 (start, accept) means "last symbol was a 0" (also accepts ε). State r1 means "last symbol was a 1." So L(B) ≈ {strings whose last symbol is 0}.
Quick test: on input "0" — A rejects (1 zero, odd), B accepts (last is 0). They disagree, so "0" ∈ L(A) △ L(B). Similarly "1" is a witness: A accepts (0 zeros, even), B rejects.
2 · Why C's states are pairs (p, r). To check whether A and B agree on a string, we run them in parallel on the same input. The current "joint state" is the pair (A's state, B's state). When the next input symbol arrives, both machines move at once: (p, r) →σ (δA(p, σ), δB(r, σ)). With 2 states in A and 2 in B, we get 2 × 2 = 4 product states.
3 · Reading the four columns of the table.
(p, r) — the product state.
0 → — where it goes on input 0. E.g. (p0, r0) →0 (p1, r0) because p0 →0 p1 in A and r0 →0 r0 in B.
1 → — same on input 1.
Accept (exactly-one) — marked when exactly one of p ∈ accept(A) and r ∈ accept(B) holds. This is the symmetric-difference accept rule: at this joint state, A says "yes" and B says "no" (or vice-versa), so the string read so far is in L(A) △ L(B).
Reachable? — can we reach this pair from the start pair (p0, r0) via some input string? Click Run reachability to do a BFS and fill this column with ✓.
4 · Verifying the four rows.
(p0, r0) — both A and B accept here (think: input "" or "00"). Two accepts → not exactly-one → not a witness.
(p0, r1) — A accepts, B rejects (think: input "1"). One accepts → exactly-one. ✓
(p1, r0) — A rejects, B accepts (think: input "0"). One accepts → exactly-one. ✓
(p1, r1) — both reject (think: input "01"). Zero accepts → not exactly-one.
5 · The verdict. Decide EQDFA by asking: is any exactly-one state reachable from the start pair? If yes, there's a string that reaches it; that string is a witness x ∈ L(A) △ L(B), proving L(A) ≠ L(B). If no, the symmetric difference is empty and L(A) = L(B). For these specific A and B, the input "1" reaches (p0, r1) in one step — a witness exists, so L(A) ≠ L(B).
EQDFA · symmetric-difference DFA C Widget 3
DFA A — even number of 0s
DFA B — last symbol is 0
DFA C · L(C) = L(A) △ L(B)
Setup
A accepts strings with an even number of 0s.
B accepts strings whose last symbol is 0.
They disagree on, for example, "01" — an odd number of 0s
so A rejects, but the last symbol is 1 so B
also rejects. Or on "0": one 0 so A rejects,
but last symbol is 0 so B accepts. The DFA C should witness one of
those disagreements.
🔊 Why this works
Why this works. Building C from A and B does real work: it is computing
two DFAs in parallel, treating the pair of current states as a single state. The
reduction EQDFA ≤ EDFA is the prototype of every reduction we'll do
later — turning a question about one machine into a question about another, where we already
know the answer is computable.
🎧 Narration
5 · ACFG: does CFG G generate string w?
For CFGs we have to be a bit careful. A naïve algorithm — "try all possible derivations" — does
not work, because there are infinitely many derivations once the grammar has any recursion
(e.g. S → SS can be expanded forever). We need a bound on how long a
derivation needs to be.
Sipser Theorem 4.7. The convert-to-CNF step makes derivations have a fixed length (2n−1 for strings of length n), so step 2's enumeration is finite. CYK is a faster O(n³) variant of this same idea.
🔊 CNF trick
The CNF trick — why exactly 2n − 1 productions
Chomsky Normal Form (CNF): every production is either
A → BC or A → a, with one exception:
S → ε for the start variable (if ε ∈ L(G)).
Any CFG can be converted to CNF.
Why CNF makes step 2 work: a binary tree with n leaves has exactly n − 1 internal nodes, so the derivation uses n − 1 branch rules (A → BC) plus n leaf rules (A → a) — exactly 2n − 1 productions total. There are only finitely many such derivations.
So we just enumerate all derivations of length 2n − 1 in
G′ and check whether any of them yields w.
There is a cleaner algorithm than enumeration — the CYK dynamic-programming algorithm
(named after its three independent inventors Cocke, Younger,
and Kasami in the 1960s) — which runs in O(n³) time.
We won't develop CYK in detail here, but it is the standard way to implement
ACFG.
Try it: bottom-up parsing table (CYK)
Below is the grammar (in CNF)
S → AB | BA, A → a, B → b
which generates strings of a's and b's where
the first and last characters differ. Type a string and click Fill table to see
the CYK table populated bottom-up. If the start variable S appears in
the top cell, the string is in the language.
ACFG via CYK Widget 4
Verdict —
How to read the table
Cell T[i, j] contains the set of variables that derive the substring
wi…wj. The bottom row is filled from the rules
A → a. Higher rows are filled by looking at all splits
wi…wk · wk+1…wj and combining via rules
A → BC. The verdict is "in L(G)" iff S
is in the top cell.
🎧 Narration
6 · ECFG: is L(G) empty?
This one is beautiful. To test whether L(G) is empty, we ask: is
there any string the start variable can derive? Equivalently: is the start variable
productive?
Define a variable to be productive if it can derive some string of terminals. We
compute the set of productive variables by an iterative marking procedure:
🔊 Marking algorithm
Marking algorithm — ECFG
Mark every variable A for which some rule A → w has w consisting only of terminals.
Repeat: mark A if there is a rule A → α in which every variable in α is already marked.
Stop when no new variables get marked.
Accept iff the start variable is not marked.
ECFG via productive-variable marking (Sipser Theorem 4.8): start with no variables marked, then in each round mark any variable that has a rule whose RHS is all-terminals or already-marked-variables. The propagation is bottom-up — A first (because of A → 0), then B (because A is now marked), then S (because both A and B are marked). C is never marked because its only rule C → CC requires C itself. L(G) ≠ ∅ ⇔ S is eventually marked.
There are only finitely many variables, so the algorithm halts in at most
|V| rounds. The marked variables are exactly the productive ones, so
we have L(G) = ∅ iff the start variable is not marked.
Try it: mark productive variables, round by round
ECFG variable marking Widget 5
Grammar (editable)
Format: each line is Var -> alt1 | alt2 | .... Use lowercase for terminals,
uppercase for variables. Start variable is the LHS of the first rule.
Round 0
Marked ∅
Verdict —
Round 0
Initially nothing is marked. Click Run one round to mark all variables
that have at least one rule consisting only of terminals.
In the default grammar, only A and D have a
rule directly producing a terminal string. From there, B
cannot become productive because its only rule keeps requiring another B.
Likewise C is stuck. So S needs an
AB or BC — both contain an unproductive
variable. The verdict will be L(G) = ∅. Edit the grammar to flip the verdict!
🔊 Module recap
The whole module in one sentence: for DFAs and CFGs, every property you would
naturally want to test — acceptance, emptiness, equivalence — reduces to a finite search,
so it can be decided.
The interactive widgets above each implement one of these algorithms. The problems below are
the ones from Sipser most directly tied to this lecture. Click each "Show hint" to reveal a
nudge, then "Show solution outline" for a worked sketch.
Sipser 4.1
Let INFINITEDFA = {⟨A⟩ : A is a DFA and L(A) is an infinite language}.
Show that INFINITEDFA is decidable.
Show hint
A DFA's language is infinite iff there is a cycle on some path from the start state to an accept state. Why?
Show solution outline
On input ⟨A⟩: (1) Mark all states reachable from the start.
(2) Mark all states from which an accept state is reachable. (3) Check whether any state
in the intersection (reachable AND can reach accept) lies on a directed cycle. Equivalently:
a state q lies on a cycle iff it can reach itself in
≥ 1 transitions. Accept iff such a "good" cycle exists. Halts because the DFA is finite.
Sipser 4.2
Let ALLDFA = {⟨A⟩ : A is a DFA and L(A) = Σ*}.
Show that ALLDFA is decidable.
Show hint
"Accepts everything" is the same as "complement accepts nothing." How do you build a DFA for the complement?
Show solution outline
Flip the accept and non-accept states of A to get A';
then L(A') = Σ* \ L(A). Now run the EDFA
decider on A': accept iff L(A') = ∅,
i.e., iff L(A) = Σ*.
Sipser 4.3
Let AεCFG = {⟨G⟩ : G is a CFG that generates ε}. Show that
AεCFG is decidable.
Show hint
"Productive" but specifically for ε: which variables can derive the empty string?
Show solution outline
Iteratively mark a variable A if it has a rule
A → α in which every symbol is either ε-yielding (already marked)
or itself; closing this off gives the set of variables that can derive ε. Accept iff the
start variable is in that set.
Sipser 4.5
Let EQDFA = {⟨A, B⟩ : L(A) = L(B)}. Give the symmetric-difference
algorithm in pseudocode and analyze its running time as a function of
|A| and |B|.
Show hint
Walk through Widget 3 (above) one cell at a time and count how many cells you fill.
Show solution outline
Construct DFA C for L(A) △ L(B) with state set
QA × QB; accept states are pairs where exactly one component
is accepting. Run EDFA on C: do BFS
from the start pair. Time is O(|QA| · |QB| · |Σ|) to build the
construction, plus the same to do reachability. So total
O(|A| · |B| · |Σ|).
Sipser 4.10
Let INFINITEPDA = {⟨M⟩ : M is a PDA and L(M) is infinite}.
Show that INFINITEPDA is decidable.
Show hint
Convert the PDA to an equivalent CFG, then use a pumping-style argument: a CFG generates an infinite language iff some variable can derive a string containing itself.
Show solution outline
Convert to CFG G. L(G) is infinite iff
some "useful" variable A (reachable from S
and productive) admits a derivation A ⇒* uAv with
uv ≠ ε. Use the marking algorithms from §6 to filter useful
variables; then for each useful A, do a graph search over the
"derives" relation to test for such a self-loop. All finite, so decidable.
Sipser 4.13
Let A = {⟨R, S⟩ : R, S are regular expressions and L(R) ⊆ L(S)}.
Show that A is decidable.
Show hint
L(R) ⊆ L(S) iff L(R) ∩ L(S)c = ∅. Use closure of regular languages under intersection and complement to build the necessary DFA.
Show solution outline
Convert R, S to DFAs. Build a DFA accepting
L(R) ∩ L(S)c (accept iff R-component
is accepting and S-component is not). Run
EDFA. Accept iff that language is empty.
🎧 Narration
One-sentence summary
🔊 Summary
Every standard yes/no question about a DFA or CFG — acceptance, emptiness, equivalence (for DFAs),
membership and emptiness (for CFGs) — has a decision algorithm, because each reduces to a finite
search (over states, transitions, or derivations of bounded length).