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)
“What will be left of the power of example if it is proved that capital punishment has another power, and a very real one, which degrades men to the point of shame, madness, and murder?”
—Albert Camus (1913–1960)
“A regular council was held with the Indians, who had come in on their ponies, and speeches were made on both sides through an interpreter, quite in the described mode,—the Indians, as usual, having the advantage in point of truth and earnestness, and therefore of eloquence. The most prominent chief was named Little Crow. They were quite dissatisfied with the white man’s treatment of them, and probably have reason to be so.”
—Henry David Thoreau (1817–1862)
“Each person calls barbarism whatever is not his or her own practice.... We may call Cannibals barbarians, in respect to the rules of reason, but not in respect to ourselves, who surpass them in every kind of barbarity.”
—Michel de Montaigne (1533–1592)