<p>Adding to the existing answer, the restriction to linear grammars also inspired similar restrictions in classical, and other grammatical models. To name a few:</p>
<ul>
<li>metalinear grammars, that is, context-free grammars where only the start symbol allows for a non-linear production</li>
<li>metalinear cooperating distributed (CD) grammar systems for modeling systems of autonomous agents</li>
<li>linear conjunctive grammars, a restriction of conjunctive grammars that captures the power of one-way real time cellular automata (trellis automata)</li>
<li>linear context-free tree languages, a model of mildly context-sensitive parsing in natural language processing</li>
</ul>

CC BY-SA 4.0
2024-09-02T09:48:53.057Z
2024-09-02T09:48:53.057Z
Hermann Gruber
<p>The first obvious reason why linear languages were introduced is that mathematicians can hardly resist, facing a lateralized notion, to consider the symmetrical version as well. For instance, in algebra, you deal with left or right inverses, but also with inverses. In ring theory, you consider left or right ideals, but also ideals, etc.</p>

<p>Since left linear and right linear grammars define regular languages, studying linear grammars just came as a natural question to study in the early days of formal language theory. Furthermore, as you mentioned in your question, linear languages appeared to be a natural intermediate class between regular and context-free languages.</p>

<p>A nice characterization of linear languages was given by Arnold L. Rosenberg: <a href="http://ac.els-cdn.com/S0019995867800068/1-s2.0-S0019995867800068-main.pdf?_tid=1ea3f9ba-9734-11e4-9805-00000aab0f6c&amp;acdnat=1420721263_86cf30224bbac3aea0e269ca01d4760c">A machine realization of the linear context-free languages</a>, <em>Information and Control</em> <strong>10</strong> (1967) 175–188. The formulation below is Proposition V.6.5 in J. Berstel's book, <em>Transduction and Context-free Languages</em>, Teubner 1979.</p>

<p>A language $L$ of $A^*$ is linear if and only if there exists a rational subset $R$ of $A^* \times A^*$ such that 
$$
L = \{ u\tilde v \mid (u, v) \in R \}
$$
where $\tilde v$ denotes the reversal of $v$. This result shows that, in a very loose sense, linear languages are a generalization of the language of palindromes.</p>

CC BY-SA 4.0
2020-11-29T12:05:25.590Z
Is it decidable whether a linear grammar generates a rational language? Comes up in [this answer](https://cs.stackexchange.com/a/132785/683).
Yuval Filmus
CC BY-SA 4.0
2020-11-29T19:21:17.320Z
@yuval-filmus After a short discussion with my colleagues, it looks like the answer to your question is negative. In a nutshell, it is well known that deciding whether a context-free language is equal to $A^*$ is undecidable. This can be proved using a linear grammar encoding the Post correspondence problem, and it turns out that the language generated by this grammar is regular iff it is equal to $A^*$.
J.-E. Pin
CC BY-SA 4.0
2020-11-29T20:47:09.723Z
That's surprising! So my intuition was wrong this time. Thanks!
Yuval Filmus
CC BY-SA 3.0
2015-01-08T13:14:18.970Z
2015-01-08T13:14:18.970Z
J.-E. Pin
<p>What is the point of linear languages? They appear to be an intermediate set of languages in between regular and context-free languages, but do they have any useful or nice properties that either have been studied, or make them worthwhile to study?</p>

CC BY-SA 3.0
2014-09-23T11:58:32.857Z
What is a linear language?
Tyson Williams
CC BY-SA 3.0
2014-09-23T14:42:43.903Z
@Tyson Williams: Maybe [this one](http://en.wikipedia.org/wiki/Linear_grammar), I guess?
Tsuyoshi Ito
CC BY-SA 3.0
2014-09-23T14:46:54.157Z
An obvious thing to try is to look for papers showing some results about linear languages and check their introductions.  Maybe you already did this and found nothing useful, but if so, I cannot see it from the question.
Tsuyoshi Ito
CC BY-SA 3.0
2014-09-23T17:13:13.247Z
Its been hard to do a proper search for them on arXiV, for example, because I keep getting extra results about languages and algorithms that run in in linear time/space.
ruadath
CC BY-SA 3.0
2014-09-23T22:29:46.067Z
In general, when you receive comments, you should consider to edit the question.
Tsuyoshi Ito
CC BY-SA 3.0
2014-09-23T22:34:22.417Z
(1) Have you checked the paper cited in the Wikipedia page?  (Disclaimer: I have not.)  (2) Have you tried searching ["linear language" "context-free language"](http://scholar.google.co.jp/scholar?hl=en&q=%22linear+language%22+%22context-free+language%22)?
Tsuyoshi Ito
<fl.formal-languages><automata-theory><grammars>
What is the importance of linear languages?
ruadath
# What is the importance of linear languages?

(Asked by: username_0 on 2014-09-23)

What is the point of linear languages? They appear to be an intermediate set of languages in between regular and context-free languages, but do they have any useful or nice properties that either have been studied, or make them worthwhile to study?

**Tags:** fl.formal-languages, automata-theory, grammars

> **Comments:**
> **username_1**: What is a linear language?  
> **username_2**: @username_1: Maybe [this one](http://en.wikipedia.org/wiki/Linear_grammar), I guess?  
> **username_2**: An obvious thing to try is to look for papers showing some results about linear languages and check their introductions.  Maybe you already did this and found nothing useful, but if so, I cannot see it from the question.  
> **username_0**: Its been hard to do a proper search for them on arXiV, for example, because I keep getting extra results about languages and algorithms that run in in linear time/space.  
> **username_2**: In general, when you receive comments, you should consider to edit the question.  
> **username_2**: (1) Have you checked the paper cited in the Wikipedia page?  (Disclaimer: I have not.)  (2) Have you tried searching ["linear language" "context-free language"](http://scholar.google.co.jp/scholar?hl=en&q=%22linear+language%22+%22context-free+language%22)?  

---

## 2 answers

### Answer by username_4 on 2015-01-08. Score: 13 | Accepted answer

The first obvious reason why linear languages were introduced is that mathematicians can hardly resist, facing a lateralized notion, to consider the symmetrical version as well. For instance, in algebra, you deal with left or right inverses, but also with inverses. In ring theory, you consider left or right ideals, but also ideals, etc.

Since left linear and right linear grammars define regular languages, studying linear grammars just came as a natural question to study in the early days of formal language theory. Furthermore, as you mentioned in your question, linear languages appeared to be a natural intermediate class between regular and context-free languages.

A nice characterization of linear languages was given by Arnold L. Rosenberg: [A machine realization of the linear context-free languages](http://ac.els-cdn.com/S0019995867800068/1-s2.0-S0019995867800068-main.pdf?_tid=1ea3f9ba-9734-11e4-9805-00000aab0f6c&acdnat=1420721263_86cf30224bbac3aea0e269ca01d4760c), *Information and Control* **10** (1967) 175–188. The formulation below is Proposition V.6.5 in J. Berstel's book, *Transduction and Context-free Languages*, Teubner 1979.

A language $L$ of $A^\*$ is linear if and only if there exists a rational subset $R$ of $A^\* \times A^\*$ such that
$$
L = \{ u\tilde v \mid (u, v) \in R \}
$$
where $\tilde v$ denotes the reversal of $v$. This result shows that, in a very loose sense, linear languages are a generalization of the language of palindromes.

> **Comments:**
> **username_5**: Is it decidable whether a linear grammar generates a rational language? Comes up in [this answer](https://cs.stackexchange.com/a/132785/683).  
> **username_4**: @yuval-filmus After a short discussion with my colleagues, it looks like the answer to your question is negative. In a nutshell, it is well known that deciding whether a context-free language is equal to $A^*$ is undecidable. This can be proved using a linear grammar encoding the Post correspondence problem, and it turns out that the language generated by this grammar is regular iff it is equal to $A^*$.  
> **username_5**: That's surprising! So my intuition was wrong this time. Thanks!  

---

### Answer by username_3 on 2024-09-02. Score: 3

Adding to the existing answer, the restriction to linear grammars also inspired similar restrictions in classical, and other grammatical models. To name a few:

* metalinear grammars, that is, context-free grammars where only the start symbol allows for a non-linear production
* metalinear cooperating distributed (CD) grammar systems for modeling systems of autonomous agents
* linear conjunctive grammars, a restriction of conjunctive grammars that captures the power of one-way real time cellular automata (trellis automata)
* linear context-free tree languages, a model of mildly context-sensitive parsing in natural language processing


---

