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:
“It was not till the middle of the second dance, when, from some pauses in the movement wherein they all seemed to look up, I fancied I could distinguish an elevation of spirit different from that which is the cause or the effect of simple jollity.—In a word, I thought I beheld Religion mixing in the dance.”
—Laurence Sterne (1713–1768)
“Someone had literally run to earth
In an old cellar hole in a byroad
The origin of all the family there.
Thence they were sprung, so numerous a tribe
That now not all the houses left in town
Made shift to shelter them without the help
Of here and there a tent in grove and orchard.”
—Robert Frost (1874–1963)
“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)
“This was Pharaoh, direct descendent of our deity Amon, god of the sun, who rules the heavens as Pharaoh rules the earth. Again, he brought treasure, gold, and precious jewels taken from our enemies. For to Pharaoh riches were power and power was to be desired. And also again he brought many captives. For is it not by slaves that one becomes even richer and then has even more power?”
—William Faulkner (1897–1962)