Is a CFL Empty or Infinite?

Deciding the emptiness of the language of a CFG

It is often easy to see if a CFG generates any strings at all by inspection, but, as always, we prefer an algorithm that will decide the question. The insight leading to such an algorithm is that all derivations end with “terminal rules”—rules that have only terminal symbols in them. A “bottom-up” approach suggests starting with a terminal rule and attempting to work our way back to the start variable. We’ll use the grammar below to illustrate the process:

It is obvious that this language contains the empty string, but let’s look for a nonempty one. Using a copy of the grammar as a temporary workspace, we’ll arbitrarily choose another terminal rule, $A\to a$, and substitute the terminal $a$ for the variable $A$ in every right-hand side rule:

The goal is to see a terminal string on the start variable’s right-hand side, so having obtained the expression $S\to aa$ ...