Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
The linear grammar is a grammar that's either left, right or left and right linear.
The context-free grammar can contain any kind of productions of non-terminals and terminals.
All linear grammars are context-free grammars.
But what is useful about distinguishing linear and context-free separately?
Let $\cal F$ and $\cal G$ be two classes of grammars, or what ever language defining devices you want. We assume that $L({\cal F}) \subset L({\cal G})$, the languages defined by the first class are included in those of the second.
Why consider both ${\cal F}$ and $\cal G$?
The most obvious reason is that the "models" in $\cal F$ are usually easier to handle to those in $\cal G$. That means it is in general easier to understand, write and analyse grammars in $\cal F$ than those in $\cal G$. So whenever it is possible to work in the smaller class we might work there.
Sometimes we want to study and understand what makes a certain type of grammar hard to handle. We know that it is undecidable whether two context-free grammars generate the same word. For regular languages (given by right-linear grammars or finite automata) it is simple to construct the intersection and decide its emptiness. Now it is a matter of curiosity to know what happens in between: what about emptyness of intersection of linear languages?
Things are not always that straightforward. Deterministic pushdown automata are strictly less powerful than the general family (which generates context-free languages). They even allow a decidable equality test which is interesting for modellers. On the other hand, except for closure under complement, they have little closure properties.
In addition to reasons of curiosity and unveiling structure, there are practical benefits.
As concrete examples, linear grammars
So it makes sense to identify if a context-free language can be represented in this fashion². We wouldn't know to look for that had we not studied linear languages/grammars on their own merit.
As @vonbrand pointed out, there are context-free languages that do not have any linear context-free grammars. According to this source, one concrete example is $\{a^i b^i a^j b^j | i, j \in \mathbb{N} \}$, which intuitively seems like a good candidate for a nonlinear language (you need to somehow glue together two different strings, each of which maintains some count, but linear grammars only let you build the front and back of the string in parallel. As a result, it's meaningful to distinguish between linear and context-free languages, since linear languages are a strict subset of the context-free languages.
