Decidable Problems

Acceptance, structural questions, and the boundary of simulation

What does it mean for a problem to be decidable?

A decision problem asks a yes-or-no question about an encoded input. We represent the set of yes-instances as a language.

For example, the graph-connectedness problem becomes

\[ CONNECTED = \{\langle G\rangle:G\text{ is a connected graph}\}. \]

A language \(L\) is decidable if some Turing machine \(D\) halts on every input and:

• accepts every \(w\in L\); and
• rejects every \(w\notin L\).

The termination requirement is essential. A machine that accepts members but may loop on nonmembers only recognizes the language.

Decidable languages lie inside the recognizable languages; some languages are not recognizable at all.

When asked whether a problem is decidable, our goal is to construct and justify an algorithm that always halts.

How to prove decidability

A typical decidability proof should specify:

1. Input: What object or objects are encoded?
2. Validation: What happens if the encoding is malformed?
3. Procedure: What finite steps does the machine perform?
4. Correctness: Why does it accept exactly the yes-instances?
5. Termination: Why can the procedure never run forever?

The algorithm may be inefficient. Decidability asks whether some terminating method exists, not whether it is practical.

Decision Problems for Regular Languages

DFA acceptance

The acceptance problem for DFAs is

\[ A_{DFA} = \{\langle B,w\rangle:B\text{ is a DFA that accepts }w\}. \]

Decider for \(A_{DFA}\)

On input \(\langle B,w\rangle\):

1. Verify that \(B\) is a valid DFA and \(w\) is a valid input string; reject malformed encodings.
2. Begin in \(B\)’s start state.
3. For each symbol of \(w\), follow the corresponding transition.
4. After the final symbol, accept if the current state is accepting; otherwise reject.

The procedure performs exactly \(|w|\) simulated transitions after validation, so it always halts. Therefore, \(A_{DFA}\) is decidable.

DFA acceptance is decidable by direct simulation, which always consumes one input symbol per step.

This illustrates a general principle:

Simulating a machine proves decidability only when the simulated computation is guaranteed to halt.

NFA acceptance

Define

\[ A_{NFA} = \{\langle N,w\rangle:N\text{ is an NFA that accepts }w\}. \]

Several terminating strategies are possible:

• convert \(N\) to an equivalent DFA and run it on \(w\); or
• maintain the set of every NFA state reachable after each input symbol, including epsilon closure.

Only finitely many states and input positions exist, so the procedure halts. Hence \(A_{NFA}\) is decidable.

Regular-expression acceptance

Define

\[ A_{REX} = \{\langle R,w\rangle:R\text{ is a regular expression describing }w\}. \]

Convert \(R\) to an equivalent NFA and apply the decider for \(A_{NFA}\). Therefore, \(A_{REX}\) is decidable.

This is an example of solving a new problem by transforming it into a previously solved one.

DFA emptiness

Define

\[ E_{DFA} = \{\langle B\rangle:B\text{ is a DFA and }L(B)=\varnothing\}. \]

View the DFA as a directed graph. Starting at the start state, run breadth-first or depth-first search through the transition graph.

• If an accepting state is reachable, reject: the labels on a path to it form an accepted string.
• If no accepting state is reachable, accept.

The graph has finitely many states, so search always terminates.

Is a regular language finite?

A DFA accepts infinitely many strings exactly when there is a cycle that:

1. is reachable from the start state; and
2. can reach an accepting state.

Such a cycle can be repeated arbitrarily many times, producing accepted strings of unbounded length.

A decider therefore:

1. removes states unreachable from the start;
2. removes states unable to reach an accepting state; and
3. checks the remaining finite graph for a directed cycle.

If a cycle exists, the language is infinite; otherwise it is finite.

Do two automata accept a common string?

Given DFAs \(B_1\) and \(B_2\), construct their product DFA for

\[ L(B_1)\cap L(B_2). \]

A product state \((q_1,q_2)\) is accepting exactly when both components are accepting. Then run the DFA-emptiness decider.

Thus it is decidable whether

\[ L(B_1)\cap L(B_2)=\varnothing. \]

Language containment

To decide whether

\[ L(B_1)\subseteq L(B_2), \]

observe that containment fails precisely when some string belongs to \(L(B_1)\) but not \(L(B_2)\):

\[ L(B_1)\subseteq L(B_2) \iff L(B_1)\cap\overline{L(B_2)}=\varnothing. \]

Regular languages are closed under complement and intersection, and their emptiness problem is decidable. Therefore containment is decidable.

Language equivalence

To decide whether two DFAs recognize the same language, test whether their symmetric difference is empty:

\[ L(B_1)=L(B_2) \iff \bigl(L(B_1)\setminus L(B_2)\bigr) \cup \bigl(L(B_2)\setminus L(B_1)\bigr) =\varnothing. \]

Equivalently, construct a product DFA that accepts whenever exactly one component is accepting and test reachability of an accepting product state.

Equivalence of regular expressions

Given regular expressions \(R_1\) and \(R_2\):

1. convert each expression to an NFA;
2. convert the NFAs to DFAs; and
3. run the DFA-equivalence decider.

Thus regular-expression equivalence is decidable, even though the two expressions may look completely different.

Is a DFA minimal?

Given a DFA \(B\):

1. remove unreachable states;
2. run a DFA-minimization algorithm, such as partition refinement; and
3. compare the number of states in the minimized DFA with the number of reachable states in \(B\).

If minimization merges no reachable states, \(B\) is minimal. The procedure acts on a finite state set and therefore terminates.

Many questions about regular languages are decidable through simulation, graph search, closure constructions, and minimization.

Decision Problems for Context-Free Languages

CFG acceptance

Define

\[ A_{CFG} = \{\langle G,w\rangle:G\text{ is a CFG that generates }w\}. \]

Trying arbitrary derivations naively is not a decider. If \(w\notin L(G)\), an unrestricted search may continue exploring derivations forever.

The key is to impose a finite search bound.

Chomsky-normal-form strategy

On input \(\langle G,w\rangle\):

1. handle \(w=\varepsilon\) separately;
2. convert \(G\) to an equivalent grammar in Chomsky normal form;
3. if \(|w|=n>0\), examine derivations of exactly \(2n-1\) steps; and
4. accept if one derives \(w\), otherwise reject.

A CNF parse tree for a string of length \(n\) has \(n\) terminal leaves and \(n-1\) binary internal nodes, so every successful derivation has \(2n-1\) productions. Only finitely many derivations of that length exist.

Alternatively, the CYK dynamic-programming algorithm determines whether \(G\) generates \(w\) in polynomial time for a CNF grammar.

Therefore, \(A_{CFG}\) is decidable.

Why this also simulates PDAs

Every PDA has an equivalent CFG. To decide whether a PDA accepts \(w\):

1. convert the PDA to an equivalent CFG \(G\); and
2. run the decider for \(A_{CFG}\) on \(\langle G,w\rangle\).

This shows that every context-free language is decidable:

\[ \mathrm{CFL}\subseteq\mathrm{DECIDABLE}. \]

The inclusion is proper, because languages such as \(\{a^nb^nc^n:n\ge0\}\) are decidable but not context-free.

CFG emptiness

Define

\[ E_{CFG} = \{\langle G\rangle:L(G)=\varnothing\}. \]

Mark variables that can generate terminal strings:

1. mark every variable with a production whose right-hand side contains only terminals, or \(\varepsilon\);
2. repeatedly mark any variable with a production whose variables are all already marked; and
3. stop when a complete pass adds no marks.

The language is nonempty exactly when the start variable is marked.

There are finitely many variables, and each iteration marks at least one new variable or terminates, so this is a decider.

CFG finiteness

Whether a CFG generates a finite language is also decidable.

One approach:

1. remove useless variables;
2. convert the grammar to a suitable normal form; and
3. inspect the variable-dependency graph for a productive cycle that can increase derived string length and lies on a path from the start variable to terminal output.

Such a cycle can be repeated to generate strings of unbounded length. Without one, only finitely many derivations can produce terminal strings.

Harder—and undecidable—CFG questions

Several questions that are easy for finite automata become undecidable for CFGs. In general, no algorithm can always determine:

• whether two CFGs generate the same language;
• whether a given CFG is ambiguous;
• whether two CFGs generate any common string;
• whether the complement of a given CFL is context-free; or
• whether a CFG generates all strings in \(\Sigma^*\).

CFG membership, emptiness, and finiteness are decidable, while several equivalence and structural questions are not.

This contrast shows that decidability depends on the question, not merely on the representation. CFG membership is decidable even though CFG equivalence is not.

The Turing-Machine Acceptance Problem

Definition

The acceptance problem for Turing machines is

\[ A_{TM} = \{\langle M,w\rangle:M\text{ is a TM that accepts }w\}. \]

This resembles \(A_{DFA}\), but a crucial difference appears when we attempt the same algorithm.

The tempting procedure

On input \(\langle M,w\rangle\):

1. simulate \(M\) on \(w\);
2. accept if \(M\) accepts; and
3. reject if \(M\) rejects.

If \(M\) loops, the simulator also loops. The procedure recognizes \(A_{TM}\) but does not decide it.

Therefore,

\[ A_{TM}\in\mathrm{RECOGNIZABLE}. \]

Direct simulation does not show that \(A_{TM}\) is decidable.

Does failure of simulation prove undecidability?

No. Showing that one proposed algorithm fails does not prove that every possible algorithm fails. Perhaps a more sophisticated method could analyze \(M\) without waiting forever.

To prove that \(A_{TM}\) is undecidable, we need a mathematical argument ruling out all possible deciders. The forthcoming proof will use contradiction and self-reference.

The TM acceptance problem introduces the gap between recognizing a computation and deciding whether it will accept.

Why finite and infinite sets enter the discussion

The undecidability proof is connected to a deeper fact: there are only countably many Turing machines but uncountably many languages.

• Every TM has a finite string encoding, so the set of TMs is countable.
• Every language over \(\Sigma\) is a subset of \(\Sigma^*\).
• Although \(\Sigma^*\) is countable, its power set \(\mathcal{P}(\Sigma^*)\) is uncountable.

Therefore, most languages cannot be recognized by any Turing machine. Counting alone establishes the existence of nonrecognizable languages, although it does not identify a natural example or prove specifically that \(A_{TM}\) is undecidable.

A useful decision-problem map

Problem	Status	Main technique
\(A_{DFA}\)	Decidable	Direct simulation
\(A_{NFA}\)	Decidable	Reachable-state sets or DFA conversion
\(A_{REX}\)	Decidable	Convert to NFA
\(E_{DFA}\)	Decidable	Graph reachability
DFA equivalence	Decidable	Product and symmetric difference
\(A_{CFG}\)	Decidable	CNF/CYK
\(E_{CFG}\)	Decidable	Generating-variable analysis
CFG equivalence	Undecidable	Proved later by reduction
CFG ambiguity	Undecidable	Proved later by reduction
\(A_{TM}\)	Recognizable but undecidable	Simulation recognizes; diagonalization proves no decider

Check your understanding

1. Why does direct simulation decide \(A_{DFA}\) but only recognize \(A_{TM}\)?
2. How does graph reachability decide DFA emptiness?
3. Why does a useful cycle characterize infiniteness of a regular language?
4. How can containment be reduced to emptiness?
5. Why is unrestricted derivation search not a decider for \(A_{CFG}\)?
6. How does Chomsky normal form impose a finite search bound?
7. Why does the failure of one algorithm not prove undecidability?
8. What additional kind of argument is needed to show that no decider can exist?