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: