20. Give the formal definition of a useful production.
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 if it occurs in at least
one derivation.
21. Give an example of a grammar with useless production.
In the grammar G with production rules P given by
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.
22. Determine whether the grammar G with P
S
A
A aA
B
bA
→
→
→
| λ
has a useless production?
Here the variable B is “useless”, therefore B
bA
→
is also useless.
There is no way to achieve S xBy
⇒
*
. Therefore B
bA
→
is a useless
production.
23. What is a λ-production?
Any production of a CFG of the form
A → λ
is called a λ-production.
24. When is a variable said to be “nullable”?
Any variable A for which the derivation
A ⇒
* λ
is possible is called “Nullable”.
25. Write a procedure to find CFG without λ-productions
(i) For all production A → λ, put A into V N .
(ii) Repeat the following steps until no further variables are added
to V N .
For all productions
B
A A
A n
→ 1 2 KK
where A 1 , A 2 , A 3 , KK A n are in V N , put B into V N .
156
Theory of Automata, Formal Languages and Computation