View source for Grammar, linear

A context-free grammar (cf. [[Grammar, context-free|Grammar, context-free]]) in which the right-hand side of each rule contains at most one occurrence of a non-terminal symbol. The class of languages generated by such grammars (linear languages) is a proper subclass of the class of context-free languages (e.g., the context-free language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044830/g0448301.png" /> is not linear). See also [[Grammar, regular|Grammar, regular]].