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

SaS|abT|abcT|abcd

TS|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.

About this article

linear grammar

Updated About encyclopedia.com content Print Article Share Article