# linear language

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

1. 1.

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

2. 2.

$A\to u$, where $u$ is a terminal word (over the set of terminal symbols $\Sigma-N$), or

3. 3.

$A\to uBv$, where $u,v$ are terminal words, and $B$ is a non-terminal symbol (in $N$).

A langauge generated by a linear grammar is called a linear language.

It can be shown that a language is linear iff it can be generated by a 1-turn 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

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=(\Sigma,N,P,\sigma)$ be a linear grammar,

## References

• 1 S. Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York (1966).
• 2 H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
• 3 J.E. Hopcroft, J.D. Ullman, , Addison-Wesley, (1969).
 Title linear language Canonical name LinearLanguage Date of creation 2013-03-22 18:55:55 Last modified on 2013-03-22 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 left-linear Defines right-linear Defines strong left-linear Defines strong right-linear Defines minimal linear grammar Defines even linear grammar Defines deterministic linear grammar