Note: for the time being, we will ignore the possibility that is in the language.

Suppose we make the following restrictions on the grammar:

- Every variable expands to at least one terminal. We can enforce this by disallowing productions of the form A.
- Every production either has at least one terminal on its right hand side (thus directly increasing the number of terminals), or it has at least two variables (thus indirectly increasing the number of terminals). In other words, we disallow productions of the form AB, where A and B are both variables.

- A sentential form of length n yields a sentence of length at least n.
- Every derivation step increases either the length of the sentential form or the number of terminals in it.
- Hence, any string w L can be generated in at most 2|w|-1 derivation steps.

Copyright © 1996 by David Matuszek

Last modified Mar 3, 1996