2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Check the definitions. Nearby you'll find proof that not all context free languages are generated by linear grammars. Usefulness, anybody's guess. Often particular cases have been studied just to check if they cover all bases, or have some interesting property. Not everytime it works out that way, but the definitions and results stay. $\endgroup$ – vonbrand Dec 29 '15 at 21:28
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

In addition to reasons of curiosity and unveiling structure, there are practical benefits.

As concrete examples, linear grammars

  1. are easier to prove correct,
  2. are easier to parse for and
  3. always have rational generating functions, obtained by algorithmically solving a linear equation system¹.

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.


  1. Which means it's "combinatorically tractable" in a certain sense.
  2. Typical beginner's mistake: making the grammar too complicated
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.