Chapter 6: Context-Free Languages J;;! 209
An_I-productions are in the required form. We repeat the construction by
considering A n - 2 • A n - 3 , .... A I'
Step 5 Modify Z;-productions. Every time we apply Lemma 6.2, we get a
new vfu'iable. (We take it as Z; when we apply the Lemma for ArProductions.)
The Zrproductlons are of the form Zi ~ aZi or Z; ~ a (where a is obtained
from Ai ~ Aia), and hence of the form Zi ~ ayor Zi ~ Aky for some k.
At the end of step 4. the R.H.S. of any Acproduction stmts with a terminal.
So we can apply Lemma 6.1 to eliminate Zi ~ Aky- Thus at the end of
step 5, we get an equivalent grammar G] in GNF.
It is easy to see that G] is in Gl\i'F. We start with G in CNG. In G any
A-production is of the form A ~ a or A ~ AB or A ~ CD. When we apply
Lemma 6.1 or Lemma 6.2 in step 2, we get new productions of the form
A ~ aa or A ~ [3, where a E V~ and [3 E V~y and a E L. In steps 3-5.
the productions are modified to the form A ~ aa or Z ~ a'a'. where a. a'
ELand a. a/ E V'(,.
Case 2 Construction of G when .A E L:
By the previous construction we get G' = (V~" L. Pl' 5) in GNF such that
L(G') = L - {A}. Define a new grammar G I as
G I = (Vy u {5'}, L. PI U {5' ~ 5. 5' ~ A}. 5')
5' ~ 5 can be eliminated by using Theorem 6.7. As 5-productions are in the
required form, 5'-productions are also in the required form. So L(G) =L(G])
and G] is in GNF. I
Remark Although we convert the given grammar to CNF in the first step.
it is not necessary to convert all the productions to the form required for CNF.
In steps 2-5. we do not disturb the productions of the form A ~ aa. a E L
and a E V\. So such productions can be allowed in G (in step 1). If we apply
Lemma 6.1 or 6.2 as in steps 2-5 to productions of the form A ~ a. where
a E vt and Ia I;:: 2. the resulting productions at the end of step 5 are in the
required form (for GNF). Hence we can allow productions of the form A ~ a,
where a E V~. and Ia I ;:: 2.
Thus we can apply steps 2-5 to a grammar whose productions are either
A ~ aa where a E V\. or A ~ a E V'(, where I a I ;:: 2. To reduce the
productions to the form A ~ a E V\. where Ia I;:: 2, we can apply step 2
of Theorem 6.8.
EXAMPLE 6.1 5
Construct a grammar in Greibach normal form equivalent to the grammar
5 -'t AA I a. A ~ 55 Ib.
Solution
The given grammar IS in C1'IF. 5 and A are renamed as A] and A 2 •
respectively. So the productions are A 1 ~ A IA 2 1 a and A 2 ~ A]A 11 b. As the
An_I-productions are in the required form. We repeat the construction by
considering A n - 2 • A n - 3 , .... A I'
Step 5 Modify Z;-productions. Every time we apply Lemma 6.2, we get a
new vfu'iable. (We take it as Z; when we apply the Lemma for ArProductions.)
The Zrproductlons are of the form Zi ~ aZi or Z; ~ a (where a is obtained
from Ai ~ Aia), and hence of the form Zi ~ ayor Zi ~ Aky for some k.
At the end of step 4. the R.H.S. of any Acproduction stmts with a terminal.
So we can apply Lemma 6.1 to eliminate Zi ~ Aky- Thus at the end of
step 5, we get an equivalent grammar G] in GNF.
It is easy to see that G] is in Gl\i'F. We start with G in CNG. In G any
A-production is of the form A ~ a or A ~ AB or A ~ CD. When we apply
Lemma 6.1 or Lemma 6.2 in step 2, we get new productions of the form
A ~ aa or A ~ [3, where a E V~ and [3 E V~y and a E L. In steps 3-5.
the productions are modified to the form A ~ aa or Z ~ a'a'. where a. a'
ELand a. a/ E V'(,.
Case 2 Construction of G when .A E L:
By the previous construction we get G' = (V~" L. Pl' 5) in GNF such that
L(G') = L - {A}. Define a new grammar G I as
G I = (Vy u {5'}, L. PI U {5' ~ 5. 5' ~ A}. 5')
5' ~ 5 can be eliminated by using Theorem 6.7. As 5-productions are in the
required form, 5'-productions are also in the required form. So L(G) =L(G])
and G] is in GNF. I
Remark Although we convert the given grammar to CNF in the first step.
it is not necessary to convert all the productions to the form required for CNF.
In steps 2-5. we do not disturb the productions of the form A ~ aa. a E L
and a E V\. So such productions can be allowed in G (in step 1). If we apply
Lemma 6.1 or 6.2 as in steps 2-5 to productions of the form A ~ a. where
a E vt and Ia I;:: 2. the resulting productions at the end of step 5 are in the
required form (for GNF). Hence we can allow productions of the form A ~ a,
where a E V~. and Ia I ;:: 2.
Thus we can apply steps 2-5 to a grammar whose productions are either
A ~ aa where a E V\. or A ~ a E V'(, where I a I ;:: 2. To reduce the
productions to the form A ~ a E V\. where Ia I;:: 2, we can apply step 2
of Theorem 6.8.
EXAMPLE 6.1 5
Construct a grammar in Greibach normal form equivalent to the grammar
5 -'t AA I a. A ~ 55 Ib.
Solution
The given grammar IS in C1'IF. 5 and A are renamed as A] and A 2 •
respectively. So the productions are A 1 ~ A IA 2 1 a and A 2 ~ A]A 11 b. As the