Decidable means an algorithm that always halts
After three guides of bad news — context-free languages are not closed under intersection or complement, and the pumping lemma hands you a recipe for proving languages like a^n b^n c^n are out of reach — it is easy to feel that grammars are slippery and hard to reason about. So here is the reassuring counterweight. Some questions about a context-free grammar are not just answerable in principle; they are answerable by an algorithm that is guaranteed to stop and print the correct yes or no, on every input, every time. That property has a name we will lean on for the rest of this ladder: the question is decidable.
Be precise about what 'decidable' demands, because the difference will matter enormously in the Turing-machine rungs ahead. A decider is an algorithm that halts on every input — never loops forever — and gives the correct answer. It is not enough to eventually say 'yes' when the answer is yes; you must also reliably say 'no' when the answer is no, in finite time. The two grammar questions in this guide both clear that bar. Later you will meet questions that do not — where the best possible procedure may run forever and you can never be sure whether it is about to answer or just stuck.
Emptiness: a marking game on the grammar
The emptiness problem asks: given a grammar G, is the language L(G) empty? Equivalently, can the start symbol derive any terminal string at all, or is it a dead machine that produces nothing? Your first instinct might be to start generating strings and see if any come out — but a grammar can generate infinitely many strings, so 'try them all' never finishes, and an empty grammar would loop forever looking for a string that is not there. We need a test that halts. The key reframing: a string exists if and only if the start symbol is generating — meaning it can reach a string made purely of terminal symbols.
So instead of chasing strings, we hunt for generating symbols, and we do it from the bottom up — exactly the dual of the non-generating symbol cleanup you saw in grammar simplification. Mark a variable 'generating' once you can prove it derives some terminal string. Start with the obvious wins and propagate upward until nothing new gets marked. This is a fixed-point computation: each pass can only add marks, there are finitely many variables, so the marking must stop. When it stops, you simply check whether the start symbol got marked.
- Seed the set. Mark every terminal as generating (a terminal trivially yields itself). Mark any variable A that has a rule A -> w where the right-hand side w is made only of terminals (including A -> epsilon).
- Propagate. Sweep through all rules. If a rule A -> X1 X2 ... Xk has every symbol on its right-hand side already marked generating, then mark A generating too. One symbol unmarked, and this rule cannot help A yet.
- Repeat the sweep until a full pass adds no new marks. Because each pass only adds marks and there are finitely many variables, this fixed point is reached after at most (number of variables) passes.
- Read off the answer. L(G) is NON-empty exactly when the start symbol S ended up marked generating. If S is unmarked, L(G) is empty — the grammar produces no string at all.
Watch it run on a tiny grammar. Take S -> A B | a, A -> A a, B -> b. Seed: 'a' and 'b' are terminals; S gets marked at once because of the rule S -> a (right side is all terminals), and B gets marked because of B -> b. Next sweep: A has only the rule A -> A a, and A is not yet marked, so A stays unmarked forever — it can never reach a pure terminal string, it just regenerates itself. Final marks: S, B (and the terminals). Since S is marked, L(G) is non-empty — and indeed S derives 'a'. Notice A is a useless non-generating symbol the test exposes for free.
Membership: does this grammar generate this string?
The membership problem is the everyday one: given a grammar G and a specific string w, is w in L(G)? This is exactly what a compiler asks of your source code — is this file a legal program according to the language grammar? A first idea is to search all derivations, trying every rule at every step. The trap is that derivations can grow then shrink (an epsilon-production or unit-production can lengthen a sentential form before it collapses), so naively searching can wander forever without ever being sure w is not derivable. To get a true decider we need to bound the search.
The clean fix is to first convert G to Chomsky normal form (CNF), which you met in the normal-forms rung. In CNF every rule is either A -> BC (exactly two variables) or A -> a (a single terminal), with epsilon allowed only for the start symbol. The payoff is a tight length bound: any non-empty string of length n is derived by exactly 2n - 1 rule applications — n of them producing the n terminals, and n - 1 of them splitting variables into pairs. No more lengthen-then-shrink wandering. Once derivations have a fixed length, the search space is finite, and a finite search always halts. That alone makes membership decidable; the next idea makes it fast.
CYK: filling a triangle of substrings
The brute-force bounded search is correct but slow. The CYK algorithm (Cocke-Younger-Kasami) replaces it with dynamic programming on a CNF grammar, deciding membership in O(n^3) time for a string of length n (with a hidden factor for grammar size). The idea is bottom-up, just like the emptiness marking: instead of asking 'can S make the whole string?' top-down, build the answer from the smallest pieces. For every substring of w, compute the set of variables that can derive exactly that substring. Begin with single characters and grow to longer and longer substrings, reusing answers you have already computed.
- Length-1 cells. For each single character w[i], find every variable A with a rule A -> w[i]. That set fills the bottom row of a triangular table — one cell per character.
- Longer cells by splitting. To fill the cell for a substring of length L, try every way to split it into a left part and a right part. If some rule A -> BC has B able to derive the left part and C the right part, put A in this cell.
- Climb the table. Process substrings in increasing length, so every split you need has already been computed below you. There are about n^2 / 2 cells and each does up to n splits — that is where the O(n^3) comes from.
- Decide. The string w is in L(G) exactly when the start symbol S appears in the single top cell, the one standing for the whole string w[1..n].
Grammar (Chomsky normal form):
S -> A B | B C A -> B A | a
B -> C C | b C -> A B | a
Decide membership of w = b a a b a (n = 5).
cell[i][L] = variables that derive the substring w[i..i+L-1].
Fill bottom (length 1) first, climb to the top (length 5).
position: 1=b 2=a 3=a 4=b 5=a
-------------------------------------------------------
L=1 {B} {A,C} {A,C} {B} {A,C}
L=2 {S,A} {B} {S,C} {S,A}
L=3 { } {B} {B}
L=4 { } {S,A,C}
L=5 {S,A,C} <-- whole string w[1..5]
S is in the top cell ==> b a a b a IS in L(G).
Each L>1 cell unions, over every split point k, the rules
A -> B C with B in the left sub-cell and C in the right one.Notice how both algorithms share one DNA: work bottom-up over finite structure and let answers accumulate until they cannot grow, which guarantees termination. That is why these questions are decidable problems about automata and grammars rather than merely recognizable. Both also generalize: emptiness for a DFA is the same reachability idea, and CYK is the general parser you will study again in the parsing rung. Honestly, O(n^3) is fine for theory but real compilers avoid it — they restrict their grammars to LL or LR classes and parse in linear time, trading generality for speed. CYK is the algorithm that proves membership is decidable for every context-free grammar.
Where the good news stops
Do not over-generalize from two wins. Decidability is question-specific, not a blanket property of grammars: the very same context-free grammars whose membership and emptiness we just settled have other questions about them that are provably undecidable — no algorithm can answer them on all inputs, ever. Asking whether two grammars generate the same language, or whether a grammar is ambiguous, or whether it generates all strings, are each undecidable. The next and final guide of this rung walks through exactly why ambiguity and equivalence fall on the wrong side of that line.
Keep the boundary crisp, because it recurs throughout the rest of this ladder. Membership and emptiness are decidable for context-free grammars; this is a genuine, useful capability you can build on. But 'context-free' is not a magic word that makes everything tractable — and even decidable does not mean cheap, since a polynomial like O(n^3) can still be slow on huge inputs. The pattern you are starting to see — some questions decidable, some not, drawn along sharp and provable lines — is the central drama of the whole theory of computation waiting in the rungs ahead.