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
George Boole , Boole, George
Boole, George
(b. Lioncoln, England, 1815; d. Cork, Ireland, 1864)
mathematics.
George Boole was the son of John Boole, a cobbler whose… Diophantus Of Alexandria , Diophantus of Alexandria
Diophantus of Alexandria
(fl. ad. 250)
mathematics.
We know virtually nothing about the life of Diophantus. The dating of hi… Domain , Domain
The domain of a relation is the set that contains all the first elements, x, from the ordered pairs (x,y) that make up the relation. In mathem… Garrett Birkhoff , Birkhoff was the son of mathematician George David Birkhoff and Margaret Grafius Birkhoff. George Birkhoff, the father, was the first American mathem… Intervening Variable , intervening variable A variable, used in the process of explaining an observed relationship between an independent and dependent variable(s), such th… Simultaneous equations , simultaneous equations Two or more equations that can be manipulated to give common solutions. In the simultaneous equations x+10y = 25 and x+y = 7,…
You Might Also Like
NEARBY TERMS
linear grammar