linear grammar

views updated

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 Aw AwB

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

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

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.