Greibach Normal Form

There is another interesting normal form for grammars that we shall not prove. Every nonempty language without e is L{G) for some grammar G each of whose productions are of the form A -+ aa, where о is a terminal and tt is a string of zero or more variables. Converting a grammar to this form is complex, even if we simplify the task by, say, starting with a Chomsky-Normal-Form grammar. Roughly, we expand the first variable of each production, until we get a terminal. However, because there can be cycles, where we never reach a terminal, it is necessary to short-circuit the process, creating a production that introduces a terminal as the first symbol of the body and has variables following it to generate all the sequences of variables that might have been generated on the way to generation of that terminal.

This form, called Greibach Normal Form, after Sheila Greibach, who first gave a way to construct such grammars, has several interesting consequences. Since each use of a production introduces exactly one terminal into a sentential form, a string of length n has a derivation of exactly n steps. Also, if we apply the PDA construction of Theorem 6.13 to a Greibach-Normal-Form grammar, then we get a PDA with no e-rules, thus showing that it is always possible to eliminate such transitions of a PDA.

* Exercise 7.1.2; Begin with the grammar:

5 -> ASB I e A -) aAS I a В -> SbS\A\bb

a) Eliminate e-productions.

b) Eliminate any unit productions in the resulting grammar.

c) Eliminate any useless symbols in the resulting grammar.

d) Put the resulting grammar into Chomsky normal form.

Exercise 7.1.3: Repeat Exercise 7.1.2 for the following grammar:

S 0.40 I IBI I BB

В S\A

С -+ 5 I e

Exercise 7.1,4: Repeat Exercise 7.1.2 for the following grammar:

S AAA I В

A aA\B

Exercise 7.1.5: Repeat Exercise 7.1.2 for the following grammar:

S aAa I bBb e

A С I a

В C\b

С CDE I e

D -> A \ B\ab

Exercise 7.1.6: Design a CNF grammar for the set of strings of balanced parentheses. You need not start from any particular non-CNF grammar.

! Exercise 7.1.7: Suppose G is a CFG with p productions, and no production

body longer than 7г. Show that ii A e, then there Is a derivation of t from

A of no more than (n - l)/{n - 1) steps. How close can you actually come to this bound?

! Exercise 7.1.8: Suppose we have a grammar G with n productions, none of them e-productions, and we we convert this grammar to CNF.

a) Show that the CNF grammar has at most O(n) productions.

b) Show that it is possible for the CNF grammar to have a number of productions proportional to n. Hint: Consider the construction that eliminates unit productions.

Exercise 7.1.9: Provide the inductive proofs needed to complete the following theorems:

a) The part of Theorem 7.4 where we show that discovered symbols really are generating.

b) Both directions of Theorem 7.6, where we show the correctness of the algorithm in Section 7.1.2 for detecting the reachable symbols.

c) The part of Theorem 7,11 where we show that all pairs discovered really are unit pairs.

*! Exercise 7.1.10: Is it possible to find, for every context-free language without e, a grammar such that all its productions are either of the form A - BCD (i.e., a body consisting of three variables), от A a (i.e., a body consisting of a single terminal)? Give either a proof or a counterexample.

Exercise 7.1.11: In this exercise, we shall show that for every context-free language L containing at least one string other than e, there is a CFG in Greibach normal form that generates L- {e}. Recall that a Greibach normal form (GNF) grammar is one where every production body starts with a terminal. The construction will be done using a series of lemmas and constructions.

a) Suppose that a CFG G has a production A -+ aBj3, and all the productions for F are В -+ 7i 72 ( 7,1. Then if we replace A -+ аВ.в by all the productions w-e get by substituting some body of a B-production for B, that is, A 071 072/? I cr/nS, the resulting grammar generates the same language as G.

In what follows, assume that the grammar G for L is in Chomsky Normal Form, and that the variables are called Ai,A-2,...,Ak.

*! b) Show that, by repeatedly using the transformation of part (a), we can convert G to an equivalent grammar in which every production body for Ai either starts with a terminal or starts with Aj, for some j > i. In either case, all symbols after the first in any production body are variables.

! c) Suppose Gi is the grammar that we get by performing step (b) on G. Suppose that Ai is any variable, and let >4 - AiQi - Aia,n be all the Aj-productions that have a body beginning with Ai. Let

Ai(h\ I 0p

be all the other ,-productions. Note that each Bj must start with either a terminal or a variable with index higher than j. Introduce a new variable Bi, and replace the first group of 7П productions by

АгРБг I I !3pB,

Bi aiBi I ffl I I amBi I qm

Prove that the resulting grammar generates tlie same language as G and Gi.

*! d) Let G2 be the granmiar that results from step (c). Note that all the A.; Ijroductions have bodies that begin with either a terminal or an Aj for j > i. Also, all the В{ productions have bodies that begin with either a terminal or some Aj. Prove that G has an equivalent grainmai in GNF. Hint: First fix the productions for Ak, then .4fc i, and so on, down to Al, using part (a). Then fix the Bi productions in any cjrder, again using part (a).

Exercise 7.1,12: Use the construction of Exercise 7.1.11 to convert the grammar

S AA\0

A -+ 55 I 1

to GNF.