Mixing Left and Right Regular Rules
If mixing of left-regular and right-regular rules is allowed, we still have a linear grammar, but not necessarily a regular one. What is more, such a grammar need not generate a regular language: all linear grammars can be easily brought into this form, and hence, such grammars can generate exactly all linear languages, including nonregular ones.
For instance, the grammar G with N = {S, A}, Σ = {a, b}, P with start symbol S and rules
- S → aA
- A → Sb
- S → ε
generates, the paradigmatic non-regular linear language.
Read more about this topic: Regular Grammar
Famous quotes containing the words mixing, left, regular and/or rules:
“How natural that the errors of the ancient should be handed down and, mixing with the principles and system which Christ taught, give to us an adulterated Christianity.”
—Olympia Brown (1835–1900)
“If we were left solely to the wordy wit of legislators in Congress for our guidance, uncorrected by the seasonable experience and the effectual complaints of the people, America would not long retain her rank among the nations.”
—Henry David Thoreau (1817–1862)
“The solid and well-defined fir-tops, like sharp and regular spearheads, black against the sky, gave a peculiar, dark, and sombre look to the forest.”
—Henry David Thoreau (1817–1862)
“A man often thinks he rules himself, when all the while he is ruled and managed; and while his understanding directs one design, his affections imperceptibly draw him into another.”
—François, Duc De La Rochefoucauld (1613–1680)