JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Problems We Can Always Decide

The last four guides built the abstract machinery — deciders, the loophole, co-recognizability, dovetailing. This one cashes it in on real questions you have been asking since the very first rung: is this DFA's language empty? Do these two automata accept the same strings? Does this grammar generate that word? Every one of them turns out to be decidable, and the proofs are short, concrete, and oddly satisfying.

From scary abstractions to homework questions

The previous four guides lived in rarefied air: a decidable language is one some decider settles on every input without ever falling through the loophole, decidability splits into recognizable plus co-recognizable, and dovetailing lets you run searches in parallel. All true, all important — but you might be wondering whether anything you actually care about is decidable. This guide is the reassuring half of the story. A whole shelf of perfectly natural questions about DFAs, NFAs, and grammars are decidable problems about automata, and we can build the deciders by hand.

First, a crucial reframing the whole rung depends on. When we ask 'is this DFA's language empty?', the input to our decider is not a string — it is a DESCRIPTION of a DFA, written out on the tape as text: its states, alphabet, transition table, start and accept states. We agree on a fixed, sensible way to write any automaton or grammar as a finite string of symbols (an encoding, written with angle brackets, so <D> means 'the encoded DFA D'). Once a machine or grammar is just a string, a question about it becomes a language: the set of all encodings that satisfy the property. Deciding the question means deciding membership in that language. That move — turning 'is this object good?' into 'is this string in this language?' — is the bridge from the abstract theory to concrete homework.

Is a DFA's language empty? Just go for a walk

Start with the cleanest case: the emptiness problem for DFAs — given <D>, does D accept NO strings at all? Your first instinct might be 'try every string and see if one is accepted', but there are infinitely many strings, so that search could loop forever and only ever gives you a recognizer, never a decider. The trick is to stop thinking about strings and start thinking about the state diagram as a plain directed graph. A string accepted by D is exactly a path from the start state to some accept state. So D accepts SOMETHING if and only if at least one accept state is REACHABLE from the start state in that graph.

Reachability in a finite graph is a finite, terminating computation — it is just a breadth-first flood fill. Mark the start state. Then repeatedly mark every state reachable in one transition from an already-marked state, until no new states get marked. Because there are only finitely many states, this stops after at most as many rounds as there are states; it is GUARANTEED to halt. When it stops, look at the marked set: if it contains any accept state, the language is non-empty; if it contains none, the language is empty. No loophole anywhere — the search is bounded by the size of the object itself, which is exactly the discipline that turns a recognizer into a decider.

DECIDER E_DFA, on input <D>:
  1. mark the start state of D
  2. repeat until no new state gets marked this round:
        for each marked state q and each input symbol a:
             mark the state delta(q, a)
  3. if any ACCEPT state of D is marked:  reject   (language is non-empty)
     else:                                accept   (language is empty)

Why it always halts: D has finitely many states, so step 2
adds at least one new mark per round and runs out of states fast.
The emptiness decider in full. It never runs D on any input; it just floods marks through D's transition graph and checks whether an accept state was reached.

Do two automata agree? The symmetric-difference trick

Next, the equivalence problem: given two DFAs A and B, do they accept exactly the same language? This one feels harder — there are infinitely many strings to compare — but it folds beautifully onto the emptiness decider you just built, using nothing but the closure properties of regular languages. The key idea is the symmetric difference of the two languages: the set of strings accepted by exactly ONE of A and B. Two languages are equal precisely when their symmetric difference is empty — there is no string on which they disagree.

  1. Write the symmetric difference as a formula: (A and not-B) or (not-A and B). In plain words, strings A accepts but B does not, together with strings B accepts but A does not.
  2. Because regular languages are closed under complement (flip the accept states), under intersection, and under union (the product construction from the regular rung), you can MECHANICALLY build a single DFA C whose language is exactly that symmetric difference. Every step is a finite construction on finite machines.
  3. Now run the emptiness decider from the previous section on <C>. If the symmetric difference is empty, A and B are equivalent — accept. Otherwise some string separates them — reject.

Savor how this works: a hard-looking question (compare two infinite languages) became an easy one (is one finite graph's accept set reachable?) by REDUCING it to a problem we had already solved. That is the same reduction muscle you will lean on in later rungs to prove things UNdecidable — only here it flows the friendly direction, carrying decidability from emptiness over to equivalence. Membership and acceptance ride along too: the acceptance problem for DFAs — does D accept this specific string w? — is the easiest of all. Just simulate D on w step by step. A DFA reads each symbol of w exactly once and halts when w runs out, so the simulation always terminates after exactly the length of w steps. A turnstile cannot loop.

Grammars get the same treatment

Everything above was about regular languages; the same spirit reaches one level up the Chomsky hierarchy to context-free grammars. Take emptiness first: given a CFG G, does it generate ANY string at all? Again, do not enumerate strings. Instead, decide which nonterminals are generating — a nonterminal can produce a string of terminals — by a bottom-up marking that mirrors the reachability flood. Mark every nonterminal that has a rule whose right side is all terminals (or empty). Then repeatedly mark any nonterminal with a rule whose right side contains only already-marked nonterminals and terminals. When nothing new gets marked, stop. The grammar's language is non-empty exactly when the start symbol ends up marked. Finitely many nonterminals means this halts — so CFG emptiness is decidable.

Membership is the showcase. Given a CFG G and a string w, does G derive w? The naive idea — try every derivation — can run forever, because a grammar with epsilon-productions or loops can build derivations that balloon and shrink without bound, so 'just search the derivations' is again only a recognizer. The fix is to first convert G to Chomsky normal form, where every rule is either A -> BC (two nonterminals) or A -> a (one terminal). In that form a derivation of a length-n string has a strictly bounded shape: exactly 2n - 1 rule applications. A bounded search is a decidable search, and the CYK algorithm does it efficiently with dynamic programming, deciding membership in time O(n^3) for a fixed grammar.

CYK on G (in Chomsky normal form) and w = a1 a2 ... an:

  table[i][i] = { A : G has rule A -> a_i }          (length-1 spans)
  for span length L = 2 .. n:
    for each start i, let j = i + L - 1:
      for each split point k in i .. j-1:
        if A -> BC,  B in table[i][k],  C in table[k+1][j]:
          add A to table[i][j]

  ACCEPT if the start symbol S is in table[1][n], else REJECT.

The table has about n^2 cells, each filled by scanning n splits: O(n^3).
The CYK membership decider: build up which nonterminals can yield each substring of w, from length-1 spans outward. The start symbol covering the whole string means w is in the language.

Where the easy answers stop

It would be a misreading to walk away thinking 'every question about machines is decidable'. The line is sharp and it matters. For DFAs, almost everything is decidable — emptiness, equivalence, membership, finiteness — because a DFA's behaviour is fully captured by a finite graph you can exhaustively analyze. Climb one rung to context-free grammars and decidability starts to fray: membership and emptiness stay decidable (you just saw why), but EQUIVALENCE of two CFGs is UNdecidable, and so is asking whether a CFG is ambiguous. The very same equivalence question, easy for DFAs, becomes impossible for grammars. Power and undecidability rise together.

So this is the rung's quiet triumph. You started the Turing-machine arc fearing the loophole — a machine that may run forever and never answer — and you end it holding a fistful of problems where the loophole simply never opens, because every search is fenced in by the finiteness of the object being analyzed. That is what 'decidable' has meant all along, made concrete: not merely that an answer exists in principle, but that a single procedure spits out the correct yes or no on EVERY input and always stops. Carry that picture forward, because the next rung shows you the first questions that genuinely break it.