# linear grammar

**linear grammar** 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 *A* → *w* *A* → *wB*

where *A* and *B* are nonterminals and *w* is a string of terminals. A *left-linear grammar* can be similarly defined: *A* → *w* *A* → *Bw*

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*S* → *aS*|*abT*|*abcT*|*abcd**T* → *S*|*cS*|*bcT*|*abc*|*abcd*

corresponds to the simultaneous linear equations *X* = {*a*}*X *∪ {*ab*,*abc*}*Y *∪ {*abcd*}*Y* = {Λ,*c*}*X *∪ {*bc*}*Y *∪ {*abc*,*abcd*}

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.

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**linear grammar**