A grammar in which each production contains at most one nonterminal in its right-hand side. Such a grammar is right-linear if a nonterminal can only occur as the rightmost symbol, i.e. if each production has one of the forms
where
A and
B are nonterminals and
w is a string of terminals. A
left-linear grammar can be similarly defined:
The right- and left-linear grammars generate precisely the regular languages.
The word linear relates to an analogy with ordinary algebra. For example, a right-linear grammar such as
corresponds to the simultaneous linear equations
where
X and
Y are sets of strings and Λ is the empty string. Union and concatenation play roles analogous to addition and multiplication. The smallest solution to the equations gives the language generated by the grammar.
See Arden’s rule.