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?

  • 2
    $\begingroup$ What is a linear language? $\endgroup$ – Tyson Williams Sep 23 '14 at 11:58
  • 1
    $\begingroup$ @Tyson Williams: Maybe this one, I guess? $\endgroup$ – Tsuyoshi Ito Sep 23 '14 at 14:42
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 23 '14 at 14:46
  • 3
    $\begingroup$ In general, when you receive comments, you should consider to edit the question. $\endgroup$ – Tsuyoshi Ito Sep 23 '14 at 22:29
  • 1
    $\begingroup$ (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"? $\endgroup$ – Tsuyoshi Ito Sep 23 '14 at 22:34

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, 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.


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.