Grammar, linear

A context-free grammar (cf. 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 $ \{ {a ^ {n} b ^ {n} a ^ {m} b ^ {m} } : {n, m = 1, 2 ,\dots } \} $ is not linear). See also Grammar, regular.