Decidable Problems

Decidable Problem

A problem (or language) is decidable (recursive) if there exists a total Turing Machine (algorithm) that always halts and gives the correct yes/no answer for every instance of the problem. This lecture shows several concrete problems about automata and grammars are decidable.

ADFA is Decidable

ADFA = { ⟨B, w⟩ | B is a DFA that accepts string w } is decidable. The TM simply simulates the DFA B on input w by following its transition function. Since a DFA always halts, the simulation is finite. Accept if simulation ends in a final state; reject otherwise.

EDFA is Decidable

EDFA = { ⟨A⟩ | A is a DFA and L(A) = ∅ } is decidable. The TM uses a graph reachability algorithm (marking) on the DFA's state diagram: 1) Mark the start state. 2) Repeatedly mark any state reachable by a transition from a marked state. 3) If no marked state is an accept state, accept (language empty); otherwise, reject.

EQDFA is Decidable

EQDFA = { ⟨A, B⟩ | A and B are DFAs with L(A) = L(B) } is decidable. The TM: 1) Constructs a DFA C for the symmetric difference L(C) = (L(A) ∩ ~L(B)) ∪ (~L(A) ∩ L(B)). 2) Tests if L(C) = ∅ using the EDFA decider. If empty, L(A)=L(B); accept. Otherwise, reject.

Symmetric Difference for Equality

The symmetric difference of two sets L(A) and L(B) contains strings in one but not the other. If the symmetric difference is empty, then L(A) and L(B) are exactly equal. This method works because regular languages are closed under complement and intersection, and we have a decider for emptiness (EDFA).

ACFG is Decidable

ACFG = { ⟨G, w⟩ | G is a CFG that generates string w } (the Membership Problem for CFGs) is decidable. The key is to convert G to Chomsky Normal Form (CNF). In CNF, any derivation of a string w of length n has exactly 2n - 1 steps (for n ≥ 1). The TM enumerates all derivations of this length and checks if any yield w. This is finite, so it halts.

Why CNF is Crucial for ACFG

In an arbitrary CFG, derivations can be arbitrarily long, leading to infinite search. Chomsky Normal Form eliminates this issue: it guarantees a fixed, finite bound on the length of derivations for a given w (2|w|-1 steps), making exhaustive search possible and ensuring the algorithm halts.

ECFG is Decidable

ECFG = { ⟨G⟩ | G is a CFG and L(G) = ∅ } is decidable. The TM uses a variable marking algorithm: 1) Mark all terminal symbols. 2) Repeatedly mark any variable A if there is a rule A → α where every symbol in α is already marked. 3) If the start variable is marked, it can generate a terminal string, so L(G) ≠ ∅ (reject). If the start variable is not marked, L(G) = ∅ (accept).

Variable Marking Algorithm (ECFG)

This algorithm determines which variables in a CFG can generate a string of terminals. It works bottom-up: terminals are "productive"; a variable is productive if it has a rule leading to a string of productive symbols. If the start symbol is productive, the language is non-empty. This process is guaranteed to terminate.

Contrast: ACFG vs. Membership for TMs

ACFG (CFG membership) is decidable, but MP = { ⟨M⟩#x | x ∈ L(M) } (TM membership/Acceptance Problem) is undecidable. This highlights a fundamental difference in power: problems about context-free grammars are often decidable, while analogous problems about Turing machines are not.

Common Proof Technique: Simulation

For automata (ADFA, EDFA, EQDFA), decidability proofs often involve direct simulation or graph algorithms (reachability) on the finite structure. The finiteness of the model (states) guarantees the simulation halts.

Common Proof Technique: Bounded Search

For grammars (ACFG), decidability proofs often involve conversion to a normal form (CNF) that bounds the search space, allowing exhaustive checking of a finite number of possibilities.

Key Takeaway: What Makes a Problem Decidable?

A problem about a computational model (DFA, CFG) is often decidable if the model has limited power or structural properties (like finiteness or normal forms) that allow an algorithm to exhaustively analyze its behavior in finite time. This fails for Turing machines due to their unbounded power.