suppose g n sigma p s is a reduced grammar we

Question

Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows:

1. Define maxrhs(G) to be the maximum length of the right hand side of  any  production.

2. While maxrhs 3 we convert G to an equivalent reduced grammar G' with smaller maxrhs.

3. a) Choose a production A → α where is of maximal length in G.

b) Rewrite α as α₁α₂ where |α₁| = |α₁|/2 (largest integer ≤ |α₁|/2) and  |α₂| = |α₂|/2 (smallest integer ≥ |α₂|/2)

c) Replace A -> α in P by A  -> α₁B and B -> α₂

If we repeat step 3 for all productions of maximal length we create a grammar G' all of whose productions are of smaller length than maxrhs.

We can then apply the algorithm to G' and continue until we reach a grammar that has maxrhs ≤ 2.