Introduction

Alright, grammar geeks, ready for another ride? We’ve seen emptiness and intersection emptiness. Now let’s ask: given two CFGs $G_1$ and $G_2$, do they generate the same language? This is the Equivalence Problem for CFGs, and good news: unlike the intersection case, equivalence is decidable (but it’s a bit more involved).

Formal Setup

Given CFGs

$$ G_1 = (V_1, Σ, R_1, S_1), \quad G_2 = (V_2, Σ, R_2, S_2), $$

the problem asks whether

$$ L(G_1) = L(G_2). $$

A decider for equivalence would output 1 if they match, and 0 otherwise.

Why It’s Tricky

CFGs aren’t closed under complement, so we can’t just check both $L(G_1) \subseteq L(G_2)$ and $L(G_2) \subseteq L(G_1)$ by taking complements. Instead, the classic approach uses conversions to pushdown automata and then checks inclusion via emptiness on intersection with a complement, leveraging decidability of some PDA operations.

High-Level Algorithm

  1. Convert each CFG $G_i$ to an equivalent Pushdown Automaton (PDA) $P_i$ (standard construction).
  2. Swap Acceptance Mode: Convert PDA $P_2$ to a PDA $P_2’$ that accepts the complement of $L(P_2)$. This is possible because deterministic PDAs are closed under complement, so we determinize $P_2$ (requires it to be unambiguous) and flip acceptance.
  3. Intersection Emptiness: Construct a PDA for $L(P_1) \cap \overline{L(P_2)}$ and test emptiness. If empty, then $L(P_1) \subseteq L(P_2)$.
  4. Symmetric Check: Swap roles to check $L(P_2) \subseteq L(P_1)$.
  5. Decide: If both inclusions hold, languages are equal.

Each step is decidable, though converting to a deterministic PDA can blow up exponentially.

Example

Suppose you have:

# G1: S -> 'a' S 'b' | ''
# Generates {"", "ab", "aabb", ...}.

# G2: T -> 'a' T 'b' | U
# U -> ''
# Same language: balanced a’s and b’s.

Following the steps above, you’d show $L(G1) = L(G2)$ via converting each to PDAs and checking both inclusions.

Why It Matters

  • Grammar Optimization: Ensuring two grammars are interchangeable.
  • Language Equivalence: Key in compiler versions, schema migrations, and ensuring backward compatibility.

Wrap-Up

CFG equivalence is a rare undecidability exception: it’s decidable, thanks to clever PDA-based constructions. Next, we’ll dive into the Emptiness Problem for Deterministic Finite Automata, which, spoiler, is trivial compared to these!