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)
“I was glad to have got out of the towns, where I am wont to feel unspeakably mean and disgraced,—to have left behind me for a season the bar-rooms of Massachusetts, where the full-grown are not weaned from savage and filthy habits,—still sucking a cigar. My spirits rose in proportion to the outward dreariness. The towns needed to be ventilated. The gods would be pleased to see some pure flames from their altars. They are not to be appeased with cigar-smoke.”
—Henry David Thoreau (1817–1862)
“It was inspiriting to hear the regular dip of the paddles, as if they were our fins or flippers, and to realize that we were at length fairly embarked. We who had felt strangely as stage-passengers and tavern-lodgers were suddenly naturalized there and presented with the freedom of the lakes and woods.”
—Henry David Thoreau (1817–1862)
“The only rules comedy can tolerate are those of taste, and the only limitations those of libel.”
—James Thurber (1894–1961)