which is in Greibach normal form.
Example 6.10
Convert the grammar
into Greibach normal form.
Here we can use a device similar to the one introduced in the construction of
Chomsky normal form. We introduce new variables A and B that are essentially
synonyms for a and b, respectively. Substituting for the terminals with their
associated variables leads to the equivalent grammar
which is in Greibach normal form.
In general, though, neither the conversion of a given grammar to Greibach
normal form nor the proof that this can always be done is a simple matter. We
introduce Greibach normal form here because it will simplify the technical
discussion of an important result in the next chapter. However, from a
conceptual viewpoint, Greibach normal form plays no further role in our
discussion, so we only quote the following general result without proof.
Theorem 6.7