Properties of Context-Free Languages

Closure properties

Why not intersection? {aⁿbⁿcᵐ} and {aᵐbⁿcⁿ} are both context-free, but their intersection is {aⁿbⁿcⁿ}, which is not (shown below). And since L₁ ∩ L₂ = complement of (L̄₁ ∪ L̄₂), closure under union plus complement would give closure under intersection; so CFLs cannot be closed under complement either.

Intersection with a regular language is the most useful closure property for proofs: if L ∩ R is not context-free for some regular R, then L is not context-free.

The pumping lemma for CFLs

A parse tree for a long enough string must have a long path, on which some variable repeats. The part of the tree between the two occurrences can be repeated or removed:

Two pieces, v and y, are pumped together. That is why a CFL can match two counts (aⁿbⁿ) but not three.

Example: {aⁿbⁿcⁿ | n ≥ 0} is not context-free. Pick s = aᵖbᵖcᵖ. Because |vxy| ≤ p, the window vxy cannot contain both a's and c's (the b-block of length p lies between them). So pumping changes at most two of the three counts, and uv²xy²z has unequal counts (or symbols out of order), so it is not in L.

def in_L(w):
    n = len(w) // 3
    return w == "a" * n + "b" * n + "c" * n

p = 3
s = "a" * p + "b" * p + "c" * p
splits = survivors = 0
for start in range(len(s)):                          # vxy = s[start:end], |vxy| <= p
    for end in range(start + 1, min(start + p, len(s)) + 1):
        for v_len in range(end - start + 1):
            for y_len in range(end - start - v_len + 1):
                if v_len + y_len == 0:
                    continue
                u, v = s[:start], s[start:start + v_len]
                x = s[start + v_len:end - y_len]
                y, z = s[end - y_len:end], s[end:]
                splits += 1
                if all(in_L(u + v * i + x + y * i + z) for i in (0, 2)):
                    survivors += 1
print(f"{splits} legal splits of {s}; splits that survive pumping with i = 0 and 2: {survivors}")

121 legal splits of aaabbbccc; splits that survive pumping with i = 0 and 2: 0

Every legal split fails, as the argument predicts. The same reasoning shows that {ww}, {aⁿ²}, {aᵖ : p prime} and {aⁱbʲcᵏ : i < j < k} are not context-free.

Decision problems

For DCFLs (given as DPDAs), equivalence is decidable (a deep result from 1997) and so is "is L = Σ*" (because DCFLs are closed under complement).

Is it context-free? A checklist

A PDA has one stack, so it can match one pair of counts at a time, in nested (last-in, first-out) order.

The last row uses a fact worth remembering: every context-free language over a one-letter alphabet is regular (Parikh's theorem).

Practice questions