THE O REM: Let G = (V, T, S, P) be a CFG. There exists an equivalent
grammar $ ( $ , $ , , $ )
G V T S P
=
that does not contain any useless variables or
productions.
Procedure: The first Part-A is to find G 1 using the algorithm.
Step 1: Set V 1 to ∅
Step 2: Repeat the following step until no more variables are added to V 1 .
For every A V
∈ for which P has a production of the form.
A x x
x
x
V
T
n
i
→
∪
1 2
1
KK ,
.
,
with all in
add A to V 1 .
Step 3: Take P 1 as all the productions in P whose symbols are all in (
)
V
T
1 ∪ .
Thus the gram mar G 1 can be gen er ated from G by the above algo rithm.
Here G
V T S P
1
1
2
1
= ( , , , ) such that V 1 con tains only vari ables A for which
A w T
⇒ ∈
*
*
The next step is to check whether every A for which A w ab
⇒ =
*
K is
added to V 1 before the procedure terminates.
Step below describes the second Part B.
“Dependency graph” is drawn to find all the variables that cannot be
reached from the start symbol S. These variables are removed from the
variable set and also all the productions involving the variables.
The resultant obtained is $ .
G
(a) Empty Pro duc tion Removal
The productions of context-free grammars can be coerced into a variety of
forms without affecting the expressive power of the grammars.
If the empty string does not belong to a language, then there is a way to
eliminate the productions of the form A → λ from the grammar.
If the empty string belongs to a language, then we can eliminate λ from all
productions save for the single production S → λ. In this case we can also
eliminate any ocurrences of S from the right-hand side of productions.
Let us illustrate this through the Example 2.4.4. Any production of a CFG
of the form
A → λ
is called a λ-production. Any variable A for which the derivation
A ⇒
* λ is pos si ble.
is called “NULLABLE”.
Con text-free Grammars
133
grammar $ ( $ , $ , , $ )
G V T S P
=
that does not contain any useless variables or
productions.
Procedure: The first Part-A is to find G 1 using the algorithm.
Step 1: Set V 1 to ∅
Step 2: Repeat the following step until no more variables are added to V 1 .
For every A V
∈ for which P has a production of the form.
A x x
x
x
V
T
n
i
→
∪
1 2
1
KK ,
.
,
with all in
add A to V 1 .
Step 3: Take P 1 as all the productions in P whose symbols are all in (
)
V
T
1 ∪ .
Thus the gram mar G 1 can be gen er ated from G by the above algo rithm.
Here G
V T S P
1
1
2
1
= ( , , , ) such that V 1 con tains only vari ables A for which
A w T
⇒ ∈
*
*
The next step is to check whether every A for which A w ab
⇒ =
*
K is
added to V 1 before the procedure terminates.
Step below describes the second Part B.
“Dependency graph” is drawn to find all the variables that cannot be
reached from the start symbol S. These variables are removed from the
variable set and also all the productions involving the variables.
The resultant obtained is $ .
G
(a) Empty Pro duc tion Removal
The productions of context-free grammars can be coerced into a variety of
forms without affecting the expressive power of the grammars.
If the empty string does not belong to a language, then there is a way to
eliminate the productions of the form A → λ from the grammar.
If the empty string belongs to a language, then we can eliminate λ from all
productions save for the single production S → λ. In this case we can also
eliminate any ocurrences of S from the right-hand side of productions.
Let us illustrate this through the Example 2.4.4. Any production of a CFG
of the form
A → λ
is called a λ-production. Any variable A for which the derivation
A ⇒
* λ is pos si ble.
is called “NULLABLE”.
Con text-free Grammars
133