Algorithms for CFLs: emptiness, finiteness, membership (CYK)

1. Are DCFLs closed under complement?
   Stuck? Peek at 3.4.1 Closure properties of CFLs and DCFLs

   • CFL closed: ∪, concat, *, reversal, h, h⁻¹, substitution, ∩R, −R. Not: ∩, complement, difference.
   • DCFL closed: complement, ∩R, ∪R, −R, h⁻¹. Not: ∪, ∩, concat, *, reversal, h.
   • Counterexample: aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ. Non-CFL proof: L ∩ R non-CFL ⇒ L non-CFL.

   Read lesson 3.4.1

2. Which grammar symbols are “generating”?
   Stuck? Peek at 3.2.1 Removing useless symbols, ε- and unit productions

   • Useful = generating + reachable. Remove non-generating first, then unreachable.
   • Nullable: A ⇒* ε. Add all versions dropping nullable occurrences; delete ε-rules; add S₀ → S | ε if needed.
   • Unit pairs by reachability over unit rules; copy non-unit bodies; delete unit rules.
   • Order: ε → unit → useless.

   Read lesson 3.2.1

3. How do you test emptiness for a DFA?
   Stuck? Peek at 2.4.2 Algorithms for regular languages

   • Membership: run. Emptiness: reachable F? Finiteness: trim + cycle (or lengths n..2n−1). Universality: complement + emptiness. Equivalence: minimize & compare, or symmetric difference empty. Containment: L₁ ∩ L̅₂ = ∅.
   • All these have always-terminating algorithms for regular languages.

   Read lesson 2.4.2

A compiler must answer “is this program grammatical?” in time proportional to a small power of its length, for any grammar. And tools must answer “does this grammar generate anything?” or “infinitely many strings?”. These three questions have algorithms for every CFG. Others — like “do two grammars generate the same language?” — have none, a fact you will be able to prove in Phase 5.

Grammar: S → AB, A → a, B → BB. Does it generate any string at all?

Prediction check

No. B only rewrites to BB and never finishes, so B is non-generating, so S is non-generating ⇒ L(G) = ∅.

Emptiness

Compute the generating symbols (3.2.1). L(G) = ∅ iff S is not generating. Always terminates.

Finiteness

Clean the grammar (no useless symbols, no ε- or unit rules; CNF works). Draw a graph with an edge A → B when B appears in a body of A. L(G) is infinite iff this graph has a cycle (a variable can derive a string containing itself).

Membership: CYK

For a CNF grammar and w of length n: fill a triangular table where cell (i, ℓ) = set of variables deriving the substring starting at i of length ℓ. Length 1 from terminal rules; longer substrings by trying every split into two parts and every rule A → BC. w ∈ L iff S is in the top cell. Time O(n³ · |G|).

What has no algorithm (for general CFGs)

For arbitrary CFGs no algorithm exists for: equivalence L(G₁) = L(G₂), universality L(G) = Σ*, ambiguity of G, whether L(G) is regular, whether L(G₁) ∩ L(G₂) = ∅. (Phase 5 builds the tools to prove such statements.) For DCFLs, universality does have an algorithm (complement is a DCFL; test emptiness).

Putting it together

• Emptiness, finiteness and membership have algorithms for every CFG.
• CYK fills a triangle bottom-up in O(n³).
• Equivalence, universality and ambiguity have no general algorithm.

CYK table (cell = variables deriving that substring)       w = b a a b a
len 5 │ {S,A,C}
len 4 │ ∅        {S,A,C}
len 3 │ ∅        {B}       {B}
len 2 │ {S,A}    {B}       {S,C}     {S,A}
len 1 │ {B}      {A,C}     {A,C}     {B}      {A,C}
         b        a         a         b        a          S ∈ top cell → ACCEPT

We can test membership, but how do we prove a language is not context-free? A pumping lemma again — this time with two pumps that move together.

1. NAT

   CYK table for n = 8 has how many cells?

   Write your answer before opening the key.

2. MSQ

   For an arbitrary CFG, which questions have an always-terminating algorithm?

   1. emptiness
   2. finiteness
   3. membership
   4. equivalence with another CFG
3. MCQ

   CYK runs in time (n = |w|):

   1. O(n)
   2. O(n²)
   3. O(n³)
   4. O(2ⁿ)
4. MCQ

   L(G) for a cleaned CNF grammar is infinite iff:

   1. G has more than one rule
   2. the variable graph has a cycle
   3. S has two rules
   4. some rule is A → a

• CFL emptiness test
• CFL finiteness test (variable graph)
• CYK algorithm
• questions with no algorithm (CFG)

1. CYK complexity?
   Reveal answer

   O(n³ · |G|), grammar in CNF.
2. How to test L(G) = ∅?
   Reveal answer

   Check whether S is generating.
3. Is CFG equivalence algorithmically solvable?
   Reveal answer

   No.