206 g Theory of Computer Science
6.4.2 GREIBACH NORMAL FORM
Greibach normal form (GNF) is another normal form quite useful in some
proofs and constructions. A context-free grammar generating the set accepted
by a pushdown automaton is in Greibach normal form as will be seen in
Theorem 7.4.
Deflnition 6.12 A context-free grammar is in Greibach normal form if every
production is of the form A ~ aa. where a E vt and a E L(a may be A),
and S ~ A is in G if A E L(G). When A E L(G), we assume that S
does not appear on the R.H.S. of any production. For example, G given by
S ~ aAB IA, A ~ bC, B ~ b, C ~ c is in GNF.
Note: A grammar in GNF is a natural generalisation of a regular grammar.
In a regular grammar the productions are of the form A ~ aa, where a E L
and a E Vv U {A}, i.e. A ~ aa, with avt and 1al s 1. So for a grammar
in GNF or a regular grammar, we get a (single) terminal and a string of
variables (possibly A) on application of a production (with the exception of
S ~ A).
The construction we give in this section depends mainly on the following
t\VO technical lemmas:
Lemma 6.1 Let G = (Vy , L. P. S) be a CFG. Let A ~ Bybe an A-production
in P. Let the B-productions be B ~ f3j 11321 ... I13,. Define
P j = (P - {A ~ By}) U {A ~ f3iyl1 sis s}.
Then. Gj = (Vy , L, Pj, S) is a context-free grammar equivalent to G.
Proof If we apply A ~ By in some derivation for ]V E L(G), we have to
*
apply B ~ f3i for some i at a later step. So A ' Z' Biy. The effect of applying
A ~ By and eliminating B in grammar G is the same as applying A ~ f3iY
for some i in grammar G!. Hence H' E L(G!), i.e. L(G) s;;; L(G!). Similarly,
instead of applying A ~ f3iY. we can apply A ~ By and B ~ f3i to get
A ~ f3iY. This proves L(G]) s;;; L(G). I
G
Note: Lemma 6.1 is useful for deleting a variable B appearing as the first
symbol on the R.H.S. of some A-production, provided no B-production has B
as the first symbol on R.H.S.
The construction given in Lemma 6.1 is simple. To eliminate B in A ~ By,
we simply replace B by the right-hand side of every B-production.
For example. using Lemma 6.1. we can replace A ~ Bab by A ~ aAab,
A ~ bBab, A ~ aaab. A ~ ABab when the B-productions are B ~ aA 1 bB I
aaiAB.
The lemma is useful to eliminate A from the R.H.S. of A ~ Aa.
Lemma 6.2 Let G = (Vy , L, P, S) be a context-free grammar. Let the set
of A-productions be A ~ Aa! I... Aa, 11311 ... 113, (f3i'S do not start with A).
6.4.2 GREIBACH NORMAL FORM
Greibach normal form (GNF) is another normal form quite useful in some
proofs and constructions. A context-free grammar generating the set accepted
by a pushdown automaton is in Greibach normal form as will be seen in
Theorem 7.4.
Deflnition 6.12 A context-free grammar is in Greibach normal form if every
production is of the form A ~ aa. where a E vt and a E L(a may be A),
and S ~ A is in G if A E L(G). When A E L(G), we assume that S
does not appear on the R.H.S. of any production. For example, G given by
S ~ aAB IA, A ~ bC, B ~ b, C ~ c is in GNF.
Note: A grammar in GNF is a natural generalisation of a regular grammar.
In a regular grammar the productions are of the form A ~ aa, where a E L
and a E Vv U {A}, i.e. A ~ aa, with avt and 1al s 1. So for a grammar
in GNF or a regular grammar, we get a (single) terminal and a string of
variables (possibly A) on application of a production (with the exception of
S ~ A).
The construction we give in this section depends mainly on the following
t\VO technical lemmas:
Lemma 6.1 Let G = (Vy , L. P. S) be a CFG. Let A ~ Bybe an A-production
in P. Let the B-productions be B ~ f3j 11321 ... I13,. Define
P j = (P - {A ~ By}) U {A ~ f3iyl1 sis s}.
Then. Gj = (Vy , L, Pj, S) is a context-free grammar equivalent to G.
Proof If we apply A ~ By in some derivation for ]V E L(G), we have to
*
apply B ~ f3i for some i at a later step. So A ' Z' Biy. The effect of applying
A ~ By and eliminating B in grammar G is the same as applying A ~ f3iY
for some i in grammar G!. Hence H' E L(G!), i.e. L(G) s;;; L(G!). Similarly,
instead of applying A ~ f3iY. we can apply A ~ By and B ~ f3i to get
A ~ f3iY. This proves L(G]) s;;; L(G). I
G
Note: Lemma 6.1 is useful for deleting a variable B appearing as the first
symbol on the R.H.S. of some A-production, provided no B-production has B
as the first symbol on R.H.S.
The construction given in Lemma 6.1 is simple. To eliminate B in A ~ By,
we simply replace B by the right-hand side of every B-production.
For example. using Lemma 6.1. we can replace A ~ Bab by A ~ aAab,
A ~ bBab, A ~ aaab. A ~ ABab when the B-productions are B ~ aA 1 bB I
aaiAB.
The lemma is useful to eliminate A from the R.H.S. of A ~ Aa.
Lemma 6.2 Let G = (Vy , L, P, S) be a context-free grammar. Let the set
of A-productions be A ~ Aa! I... Aa, 11311 ... 113, (f3i'S do not start with A).