# What is the importance of linear languages?

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?

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

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.
• @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^*$. Nov 29, 2020 at 19:21