CS 154. Winter 1996. Handout 8, February 5, 1996.

Based on a CS254 handout of Vaughan Pratt, Winter 1994.

Context-Free Languages

1 Definitions

Definition 1. A context-free grammar (CFG) G = (V, Σ, Π, S) consists of a finite set V of variables (aka nonterminals) A_{1}, A_{2},…, A_{n}, a finite alphabet Σ, a finite set Π ⊂ V × (V ∪ Σ)^{∗} of productions A → α where A ∈ V and α ∈ (V ∪ Σ)^{∗}, and a nonterminal S ∈ V, the start symbol.

Definition 2. A solution to a CFG (V, Σ, Π, S) is a function s : V → 2^{Σ^{∗}} from variables to languages (equivalently a V -tuple of languages ⟨L_{1}, L_{2},…, L_{n}⟩) such that for all productions A → α, s(A) ⊇ s(α) where s′ : (V ∪ Σ)^{∗} → 2^{Σ^{∗}} extends the domain of s by defining s′(A) = s(A) for all A ∈ V, s′(a) = {a} for all a ∈ Σ and s(α_{1} ⋯ α_{k}) = s′(α_{1}) ⋯ s′(α_{k}). The pointwise inclusion order on solutions s, t is the partial order defined by s ≤ t just when s(A) ⊆ t(A) for all A ∈ V.

Definition 3. The context-free language L(G) generated by the CFG G with start symbol S is the value of L_{S} in the least solution to G.

We now show in either of two ways that definition 3 is a well-definition in that there exists such a solution and it is unique.

Theorem 1. There exists a unique solution to a CFG that is least (less or equal to every solution) with respect to the pointwise inclusion order on solutions.

Proof. Uniqueness. Let s, s′ be two least solutions. Then for all A, s(A) ⊆ s′(A) ⊆ s(A) whence s(A) = s′(A).

Existence. There exists at least one solution, namely the maximal solution (Σ^{∗})^{V} assigning Σ^{∗} to all variables. We give two constructions of the least solution, top-down and bottom-up.

1. Top-down. Form the pointwise intersection m of all solutions, that is, m(A) is the set of those strings that appear in s(A) for every solution s. Certainly m is less than every solution, so it suffices to show that m is a solution. For if not, then for some production A → α there exists a string u ∈ Σ^{∗} in m′(α) but not in m(A). Now u must be of the form u_{1} … u_{k} where u_{i} ∈ m′(α_{k}) for all α_{k} in α. But each of these u_{i}’s must appear in every solution s since m′(α_{k}) ⊆ s′(α_{k}), whence u ∈ s′(α) for every solution s. But then u must appear in s(A) for every solution s, by definition of a solution, a contradiction.

2. Bottom-up. We construct a sequence of functions m_{i} : V → 2^{Σ^{∗}} each less or equal to all solutions, and show that its pointwise union, defined by m(A) = ⋃_{i} m_{i}(A) for all A ∈ V, itself necessarily less or equal to all solutions, is a solution.

Take m_{0}(A) = ∅. Take m_{i+1}(A) = m_{i}(A) ∪ ⋃_{A→α∈Π} m′_{i}(α), the union of m_{i}(A) and all m_{i}(α) for productions A → α having A on their left side.

Given a solution s, we argue by induction that each m_{i} is less than s. The base case is self-evident. By the induction hypothesis m′_{i}(α_{j}) ⊆ s′(α_{j}) for every right side α_{j} whence m_{i+1}(A) ⊆ s(A). It follows that the union m of all the solutions is also less than s, since every string in m(A) must appear in m_{i}(A) for some i.

Now suppose m is not a solution. Then for some production A → α there exists a string u ∈ Σ∗ in m′(α) but not in m(A). By construction of m, u must appear in m_{i}(α) for some i. But then u ∈ m_{i+1}(A), a contradiction.

Notice the similarities and differences near the end of each construction. In both cases we showed that for all productions A → α, every u ∈ m′(α) must belong to m(A). Going top-down, we used the fact that u must belong to s(A) for every solution. Going bottom-up, we found u in some m_{i}(A). The appearance of “every” in one method and “some” in the other is characteristic of such dual solutions to problems.

2 Derivations

The bottom-up construction may be associated with derivations (B&F p.342) as follows. Given a CFG G, define n_{i} : V ∪ Σ → (V ∪ Σ)^{∗} inductively as n_{i}(a) = {a} for all i and all a ∈ Σ, and for all A ∈ V define n_{0}(A) = {A}, n_{i+1}(A) = n_{i}(A) ∪ ⋃_{A→α∈Π} n_{i}(α). (The difference from m_{i} in the bottom-up construction is that nonterminals can appear in n_{i}(A); the strings of n_{i}(A) are called sentential forms.)

Theorem 2. A CFG G has a derivation S ⇒^{∗} α if and only if α ∈ n(S).

Proof. Exercise 1.

We associate derivations with the bottom-up construction as follows.

Theorem 3. m_{i}(A) consists of those strings of n_{i}(A) containing no nonterminals.

Proof. Exercise 2.

3 NSA ≡ CF L

Theorem 4. The class NSA of languages accepted by NSA’s coincides with the class CFL of context-free languages.

Proof. CF L ⊆ NSA. See text.

NSA ⊆ CF L. Define an NTA to be a control-less machine [stack,input] whose stack instructions are POP a, POP a;PUSH b;PUSH c, and NOOP, with a distinguished stack symbol S, which initializes its stack to hold S and accepts only when the input is empty and S is on the stack.

Lemma. Every NTA can be simulated by an NSA and vice versa.

Proof. It is easy to see how to simulate the pop-push-push instruction of an NTA with a threeinstruction NSA subprogram, establishing one direction.

To simulate an NSA with an NTA, the idea will be to store the current control state on the top of the stack alongside the top stack symbol. The hard part is popping the stack, which erases the current control. Here we use the nondeterminism to guess, at the time we push, the state we want to be in later on when we pop, checking that the guess was correct when we eventually pop.

To this end, we take the NTA stack alphabet to be Q × Γ × Q where Q and Γ are the control set and stack alphabet of the NSA. Simulate (q_{i} → q_{j}, POPA, in) (where in is any input operation or NOOP) by (POP(q_{i}, A, q_{j}), in). Simulate each instruction (q_{i} → q_{j}, PUSHA, in) with Q × Γ × Q instructions of the form (POP (q_{i}, B, q_{k}); PUSH (q_{m}, B, q_{k}); PUSH (q_{j}, A, q_{m}), in), one for each NTA symbol (q_{m}, B, q_{k}). Simulate each instruction (q_{i} → q_{j}, NOOP, in) with (POP (q_{i}, B, q_{k}); PUSH (q_{j}, B, q_{k}); PUSH (q_{w}, A, q_{w}), in), where q_{w} is a new state not in Q, associated with an additional NTA instruction (POP(q_{w}, A, q_{w}), NOOP).

This works as follows. Before pushing (q_{j}, A,?) on top of (q_{i}, B, q_{k}), guess that when we pop it back we will want to be in state q_{m}. Do this by replacing it by (q_{m}, B, q_{k}) and then pushing (q_{j}, A, q_{m}). The last component creates a link between these two cells that ensures that when we later pop while jumping to state q_{j}, that state will miraculously appear on the stack, achieved by how we use the POP instruction. The details and rest of this construction should now be straightforward.

Exercise 3. Design an NUA [stack,input] having stack alphabet Q × Γ and different instruction set from the above NTA, such that the lemma follows with NUA in place of NTA. Prove the new lemma.

Given any NTA M, it is now straightforward to construct a CFG G generating the language accepted by M. Take V = Γ and S = S. Define Π as follows.

For each instruction (POP A, SCAN b), a rule A → b. For each instruction (POP A, NOOP), a rule A → Λ. For each instruction (POP A;PUSH B;PUSH C, SCAN d), a rule A → dCB. For each instruction (POP A;PUSH B;PUSH C, NOOP), a rule A → CB. For each instruction (NOOP, SCAN a) and for each variable A, a rule A → aA. The claimed connection should now be clear.