Context-Free Languages: Simplification & Normal Forms

a non-generating symbol

Imagine a vending machine button that, whenever you press it, only ever offers you more buttons to press, never an actual snack. No matter how long you keep pressing, you never get food. A non-generating symbol is a grammar variable just like that button: it can never bottom out into a finished string of terminals.

Formally, a variable A is generating if there is some derivation A =>* w where w is a string made only of terminal symbols (possibly the empty string). A non-generating symbol is one for which no such derivation exists — every rule for it keeps producing variables that themselves can never finish. You find the generating symbols by a simple bottom-up marking: first mark every terminal and any variable with a rule A -> w where w is already all-generating (e.g. A -> a); then repeat, marking any variable that has a rule whose right-hand side is now entirely generating, until nothing new gets marked. Whatever is left unmarked is non-generating.

Non-generating symbols and the rules mentioning them are deleted as part of useless-symbol removal, and crucially this is done BEFORE the unreachable-symbol pass. If, after deleting non-generating symbols, the start symbol itself is gone (non-generating), then the grammar's language is empty — which is actually how you decide the emptiness problem for context-free grammars. The marking procedure runs in time polynomial in the grammar's size, so detecting non-generating symbols is cheap.

S -> AB | a, A -> aA, B -> bB. Marking: terminals a,b are generating; S is generating via S -> a. But A only has A -> aA (right side mentions A, never all-terminal) and B only has B -> bB, so neither A nor B ever gets marked — both are non-generating, and S -> AB is dead.

A variable is generating only if some rule lets it eventually reach an all-terminal string.

Non-generating is NOT the same as unreachable. A symbol can be perfectly reachable from the start yet still non-generating (you can get to it, but it dead-ends); the two tests are independent and both are needed.

Also called
non-productive symboldead variablenon-terminating variable非生產性符號死變數