Chapter 6: Context-Free Languages ~ 221
any production of G. Show that there exists an equivalent grammar G I m
CNF, which has at most (k - l)IPI + ILl productions.
Solution
In step 2 (Theorem 6.8). a production of the form A ~ XIX::: ... X il is
replaced by A ~ Yj Y:::, ...• Y ll where Y i = Xi if Xi E V N and Y i is a new
variable if Xi E I.. We also add productions of the form Y i ~ Xi whenever
Xi E I. As there are II I terminals, we have a maximum of II. I productions of
the form Y i ~ Xi to be added to the new grammar. In step 3 (Theorem 6.8),
A ~ AjA::: ... An is replaced by n - 1 productions, A ~ AIDj. D] ~ A 2 D:::
... D Il
_::: ~ An_jAil' Note that n S k. So the total number of new productions
obtained in step 3, is at most (k - 1) 1P I. Thus the total number of productions
in CNF is at most (k - l)IPI + II. I·
Example 6.24
Reduce the following CPG to GNF:
S ~ ABbla,
A ~ aaA.
B ~ hAb
Solution
The valid productions for a grammar in GNF are A ~ a (X, where a E L,
0; E V~v.
So, S ~ ABb can be replaced by S ~ ABC, C ~ b.
A ~ aaA can be replaced by A ~ aDA. D ~ a.
B ~ hAb can be replaced by B ~ hAC. C ~ b.
So the revised productions are:
S ~ ABC I a,
A ~ aDA,
B ~ hAC.
C ~ b.
D ~ a.
Name S, A, B, C, D as A b A:::, A 3 , A 4 • As.
Now we proceed to step 2.
Step 2 G 1 = ({AI, A:::, A 3 , A 4 , As}, {a, b}, PI, AI) where PI consists of
Al ~ A:::Afi41 a, A::: ~ aAsA:::, A 3 ~ bA:::A 4 , A 4 ~ b. As ~ a
The only production to be modified using step 4 (refer to Theorem 6.9)
is AI ~ A:::Afi4'
Replace Al ~ A:::Afi4 by Al ~ aAsA:::Afi4'
The required grammar in Gr-..Tf is
G 2 = ({A b A 2 . ,13, A~, As}, {a, b}, P b AI) where P 2 consists of
AI ~ aAsAfi41 a
A 2 ~ aAsA2
A 3 ~ bA 2 A 4 ,
A 4 ~ b,
As ~ a