## Quick Reference

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.

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.