Assume that A and B are different variables and that
B
y y
y n
→ 1 2
| |
| .
LL
is the set of all productions in P which have B as the left side.
Let $ ( , , , $ )
G V T S P
=
be the grammar in which $
P is constructed by deleting
A x B x
→ 1
2
from P, and adding to it
A x y x x y x
x y x
n
→ 1 1 2 1 2 2
1
2
|
| |
.
L
Then L G L G
( $ )
( )
=
.
Sub sti tu tion Rule
A production A x Bx
→ 1 2 can be eliminated from a grammar if we put in its
place the set of productions in which B is replaced by all strings it derives in
one step. In this result, it is necessary that A and B are different variables.
An illustration is given in examples 2.4.1 and 2.4.2.
2.4.2 Abol ishing Use less Pro duc tions
In the grammar G with P,
S
aSb
A
A aA
→
→
| |
.
λ
the production S
A
→ does not play any role because A cannot be transformed
into a terminal string. ‘A’ can occur in a string derived from S, this can never
lead to a sentential form. Hence this production rule can be removed, which
does not affect the language.
Definition: Let G V T S P
= ( , , , ) be a CFG.
A variable A V
∈ is said to be “useful” iff there is at least one w L G
∈ ( )
such that
S xAy w
⇒
⇒
*
*
with x, y in (
)
*
V T
∪
, i.e., a variable is useful iff it occurs in at least one
derivation.
Illustration: Consider the grammar G with P
S
A
A aA
B
bA
→
→
→
|
.
λ
Here the variable B is said to be “useless”, hence the production B
bA
→
is
also “useless”. There is no way to achieve S xBy
⇒
*
.
132
Theory of Automata, Formal Languages and Computation