Introduction

Alright, time to switch gears, now we look at Context-Free Grammars (CFGs). Given a CFG $G$, can you tell if it generates no strings (i.e., its language is empty)? Good news: unlike Turing machines, this one is decidable, and there’s a neat algorithm to check it.

Formal Setup

A CFG is a tuple

$$ G = (V, Σ, R, S) $$

where

  • $V$ is a finite set of nonterminals,
  • $Σ$ is a finite set of terminals,
  • $R$ is a set of production rules of the form $A \to α$ with $A\in V$, $α\in (V\cupΣ)^*$,
  • $S\in V$ is the start symbol.

We define

$$ L(G) = {,w \in Σ^* \mid S \xRightarrow{*} w}. $$

The Emptiness Problem for CFGs asks: is $L(G) = ∅$?

Example Grammars

# Grammar G1:
# S -> A B
# A -> 'a' | A 'a'
# B -> 'b'
# Here S can derive "ab", "aab", "aaab", etc., so L(G1) ≠ ∅.

# Grammar G2:
# S -> A B
# A -> A 'a'
# B -> 'b' B
# Both A and B are left-recursive, but neither can produce a terminal-only string.
# Thus L(G2) = ∅.

  • Question: Does G1 generate any string? Answer: Yes, for example “ab”.

  • Question: Does G2 generate any string? Answer: No, the nonterminals never bottom out to terminals, so the language is empty.

Algorithm (Detecting Generating Nonterminals)

  1. Initialize a set $Gen = ∅$.

  2. Loop until no change:

    • For each rule $A \to α$ in $R$, if every symbol in $α$ is either a terminal or already in $Gen$, add $A$ to $Gen$.

  3. Check: if the start symbol $S$ is in $Gen$, then $L(G) ≠ ∅$; otherwise $L(G) = ∅$.

This runs in time polynomial in the size of the grammar.

Why It Matters

  • Compiler Design: Ensuring grammars actually produce something is crucial when designing programming language parsers.
  • Error Detection: Empty or ill-formed grammars often point to mistakes in grammar rules.
  • Contrast with TMs: It’s satisfying to see that CFGs, despite being powerful, still admit this decidability result.

Wrap-Up

We’ve seen a simple, efficient way to test CFG emptiness, just find which nonterminals can generate terminals and see if you reach the start symbol. Up next: the Finiteness Problem for CFGs, spoiler: also decidable, but with a slightly more involved algorithm!