grammars. We now make a similar distinction between languages.
Definition 8.1
A context-free language L is said to be linear if there exists a linear context-free
grammar G such that L = L (G).
Clearly, every linear language is context-free, but we have not yet established
whether or not the converse is true.
Example 8.5
The language L = {a n b n : n > 0} is a linear language. A linear grammar for it is
given in Example 1.11. The grammar given in Example 1.13 for the language L
= {w : n a (w)= n b (w)} is not linear, so the second language is not necessarily
linear.
Of course, just because a specific grammar is not linear does not imply that
the language generated by it is not linear. If we want to prove that a language is
not linear, we must show that there exists no equivalent linear grammar. We
approach this in the usual way, establishing structural properties for linear
languages, then showing that some context-free languages do not have a required
property.
Theorem 8.2
Let L be an infinite linear language. Then there exists some positive integer m,
such that any ω ε L with |ω| ≥ m can be decomposed as w = uvxyz with
such that