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