linear language
A formal grammar $G=(\mathrm{\Sigma},N,P,\sigma )$ is said to be linear if each of its productions has the form $A\to x$, where $A$ is a nonterminal, and $x$ is a word over $\mathrm{\Sigma}$ containing no more than one occurrence of a nonterminal. In other words, a production in $G$ has one of the following forms:

1.
$A\to \lambda $ (the empty word)

2.
$A\to u$, where $u$ is a terminal word (over the set of terminal symbols $\mathrm{\Sigma}N$), or

3.
$A\to uBv$, where $u,v$ are terminal words, and $B$ is a nonterminal symbol (in $N$).
A langauge generated by a linear grammar is called a linear language.
By definition, any linear language is contextfree. However, not all contextfree languages are linear. A Dyck language^{} is an example of a nonlinear contextfree language.
Furthermore, every regular language is linear, since any production of a regular grammar has one of the above three forms, except $v=\lambda $ in the last form. The converse^{} is also not true. For example, the language^{} $\{{a}^{n}{b}^{n}\mid n\ge 0\}$ is known to be not regular^{} (apply the pumping lemma^{}), but it is linear, generated by the following productions $\sigma \to \lambda $, $\sigma \to a\sigma b$.
It can be shown that a language is linear iff it can be generated by a 1turn pushdown automaton (once it starts popping, it never pushes again).
As we have seen above, a regular grammar is a more restricted form of a linear grammar. Various restrictions^{} may be placed on a linear grammar $G$:

•
$G$ is right linear if $v=\lambda $ is the third form above (so a regular grammar is also known as a right linear grammar)

•
$G$ is strong right linear if it is right linear, and there are no productions of the second form

•
$G$ is left linear if $u=\lambda $ in the third form above

•
$G$ is strong left linear if it is left linear, and there are no productions of the second form
However, it can be shown that all of the restricted types of linear grammars mentioned above are equivalent^{}, in the sense that a language generated by one restricted type can be generated by all other restricted types.
Remark. Subfamilies of the family of linear languages can be formed by putting restrictions on the linear grammars. In some cases, the subfamily formed properly sits between the family of regular languages and the family of linear languages. Here are some examples: let $G=(\mathrm{\Sigma},N,P,\sigma )$ be a linear grammar,

•
$G$ is minimal^{} if $N=\{\sigma \}$, and there is exactly one production of the form $\sigma \to a$, where $a\in \mathrm{\Sigma}$ such that $a$ occurs in no other productions. Therefore, if $\sigma \to u$ is another production of $G$, then $u\notin \mathrm{\Sigma}$, and $a$ does not occur in $u$.

•
$G$ is even if every production having the third form above ($A\to uBv$) has the property that $u=v$ (same length). It can be shown that every regular language can be generated by an even linear grammar, and that the converse is not true.

•
$G$ is deterministic^{} if every production has the form $A\to aW$, where $a\in \mathrm{\Sigma}N$, and $W$ is either the empty word $\lambda $, or in $N{(\mathrm{\Sigma}N)}^{*}$. Furthermore, every $(A,a)\in N\times (\mathrm{\Sigma}N)$ corresponds to at most one production.
References
 1 S. Ginsburg, The Mathematical Theory of ContextFree Languages, McGrawHill, New York (1966).
 2 H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation. PrenticeHall, Englewood Cliffs, New Jersey (1981).
 3 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation^{} to Automata, AddisonWesley, (1969).
Title  linear language 
Canonical name  LinearLanguage 
Date of creation  20130322 18:55:55 
Last modified on  20130322 18:55:55 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  8 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q45 
Classification  msc 68Q42 
Synonym  left linear 
Synonym  right linear 
Synonym  strong left linear 
Synonym  strong right linear 
Related topic  MetalinearLanguage 
Defines  linear grammar 
Defines  leftlinear 
Defines  rightlinear 
Defines  strong leftlinear 
Defines  strong rightlinear 
Defines  minimal linear grammar 
Defines  even linear grammar 
Defines  deterministic linear grammar 