Eliminate the variable B from the grammar S aSB|bB B aA|b. 2 Complete the proof of Theorem 6.1 by showing that (Given Below) S *G wS * w implies S...

1. Eliminate the variable B from the grammar

S → aSB|bB

B → aA|b.

2 Complete the proof of Theorem 6.1 by showing that (Given Below)

S ⇒*Gˆ wS ⇒*Ĝ w

implies

S ⇒*G w.S ⇒*G w

3. In Theorem 6.1, why is it necessary to assume that A and B are different variables?

THEOREM 6.1

Let G = (V, T, S, P) be a context-free grammar. Suppose that P contains a production of the form

A → x1Bx2.

Assume that A and B are different variables and that

B → y1 |y2|ꞏꞏꞏ|yn

is the set of all productions in P that have B as the left side. Let Ĝ = (V, T, S, PˆP̂ ) be the grammar in which PˆP̂ is

constructed by deleting

A → x1Bx2 (6.1)

from P, and adding to it

A → x1y1x2 |x1y2x2|ꞏꞏꞏ|x1ynx2.

Then

L (Ĝ) = L (G).

Proof: Suppose that w ∈ L (G), so that

S⇒*G w.S⇒*G w.

The subscript on the derivation sign ⇒ is used here to distinguish between derivations with different grammars. If this

derivation does not involve the production (6.1), then obviously

S⇒*Gˆ w.S⇒*Ĝ w.

If it does, then look at the derivation the first time (6.1) is used. The B so introduced eventually has to be replaced; we

lose nothing by assuming that this is done immediately (see Exercise 18 at the end of this section). Thus

S ⇒*G u1 Au2 ⇒ G u1x1Bx2u2 ⇒ G u1x1 yjx2u2.S ⇒*G u1 Au2 ⇒ G u1 x1 B x2 u2

⇒ G u1 x1 yj x2 u2.

But with grammar Ĝ we can get

S ⇒*Gˆ u1 Au2 ⇒ Gˆ u1 x1 yj x2u2.S ⇒*Ĝ u1 Au2 ⇒ Ĝ u1 x1 yj x2 u2.

Thus we can reach the same sentential form with G and Ĝ. If (6.1) is used again later, we can repeat the argument. It

follows then, by induction on the number of times the production is applied, that

S ⇒*Gˆ w.S ⇒*Ĝ w.

Therefore, if w ∈ L (G), then w ∈ L (Ĝ).

By similar reasoning, we can show that if w ∈ L (Ĝ), then w ∈ L (G), completing the proof.

4. Convert the grammar

S → AB|aB,

A → abb|λ,

B → bbA

into Chomsky normal form.

5.Convert the grammar

S → ab |aS| aaS|aSS

into Greibach normal form.