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)
“July 4. Statistics show that we lose more fools on this day than in all the other days of the year put together. This proves, by the number left in stock, that one Fourth of July per year is now inadequate, the country has grown so.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“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)
“Logic teaches rules for presentation, not thinking.”
—Mason Cooley (b. 1927)