In computer science, a linear grammar is a context-free grammar that has at most one nonterminal in the right-hand side of each of its productions.
An example of a linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules It generates the language
Two special types of linear grammars are the following: Each of these can describe exactly the regular languages.
Observe that by inserting new nonterminals, any linear grammar can be replaced by an equivalent one where some of the rules are left-linear and some are right-linear.
For instance, the rules of G above can be replaced with However, the requirement that all rules be left-linear (or all rules be right-linear) leads to a strict decrease in the expressive power of linear grammars.
For example, the language of even-length palindromes on the alphabet of 0 and 1 has the linear grammar S → 0S0 | 1S1 | ε.
An arbitrary string of this language cannot be parsed without reading all its letters first which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string.
Since nondeterministic context-free languages cannot be accepted in linear time [clarification needed], linear languages cannot be accepted in linear time in the general case.
[2] A language is linear iff it can be generated by a one-turn pushdown automaton – a pushdown automaton that, once it starts popping, never pushes again.
Linear languages are closed under union.
playing the role of the linear grammars for
is again a linear language; in other words, the linear languages are closed under intersection with regular sets.
[3] As a corollary, linear languages form a full trio.
Full trios in general are language families that enjoy a couple of other desirable mathematical properties.
Linear languages are not closed under intersection.
See pumping lemma for context-free languages.
As a corollary, linear languages are not closed under complement (as intersection can be constructed by de Morgan's laws out of union and complement).