Example 5.1
The grammar G = ({S}, {a, b}, S, P), with productions
is context-free. A typical derivation in this grammar is
This, and similar derivations, make it clear that
The language is context-free, but as shown in Example 4.8, it is not regular.
Example 5.2
The grammar G, with productions
is context-free. We leave it to the reader to show that
Both of the above examples involve grammars that are not only context-free,
but linear. Regular and linear grammars are clearly context-free, but a contextfree grammar is not necessarily linear.
Example 5.3