A → x 1 Bx 2 .
Assume that A and B are different variables and that
B → y 1 |y 2 |…|y n
is the set of all productions in P that have B as the left side. Let = (V, T, S, )
be the grammar in which is constructed by deleting
from P, and adding to it
Then
Proof: Suppose that w ∈ L (G), so that
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
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
But with grammar we can get
Thus we can reach the same sentential form with G and . If (6.1) is used again
Assume that A and B are different variables and that
B → y 1 |y 2 |…|y n
is the set of all productions in P that have B as the left side. Let = (V, T, S, )
be the grammar in which is constructed by deleting
from P, and adding to it
Then
Proof: Suppose that w ∈ L (G), so that
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
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
But with grammar we can get
Thus we can reach the same sentential form with G and . If (6.1) is used again