Is a CFL Empty or Infinite?

Learn how to decide the emptiness and infiniteness of the language of a CFG.

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:

Get hands-on with 1200+ tech skills courses.