Linear grammar

In computer science, a grammar is linear if it is context-free and all of its productions' right hand sides have at most one nonterminal.

A "linear language" is a language generated by some linear grammar.

Example

A simple linear grammar is "G" with "N" = {S}, Σ = {a, b}, "P" with start symbol "S" and rules: S → aSb: S → εIt generates the language $\{\; a^ib^i\; |\; i\; >=\; 0\}$.

Relationship with regular grammars

Two special types of linear grammars are the following:
* the "left-linear" or left regular grammars, in which all nonterminals in right hand sides are at the left ends;
* the "right-linear" or right regular grammars, in which all nonterminals in right hand sides are at the right ends.Collectively, they are known as the regular grammars; both can describe exactly the regular languages.

Another special type of linear grammar is the following:
* linear grammars in which all nonterminals in right hand sides are at the left or right ends, but not necessarily all at the same end.

By inserting new nonterminals, every linear grammar can be brought into this form without affecting the language generated.For instance, the rules of "G" above can be replaced with: S → aA: A → Sb: S → ε

Hence, linear grammars of this special form can generate all linear languages.

Expressive power

We have seen that all regular languages are linear; the example gave a linear, non-regular language.All linear languages are context-free by definition; a simple example of a context-free, non-linear language is the Dyck language of well-balanced bracket pairs.

Hence, the regular languages are a proper subset of the linear ones, which in turn are a proper subset of the context-free languages.