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:
“Give me Catholicism every time. Father Cheeryble with his thurible; Father Chatterjee with his liturgy. What fun they have with all their charades and conundrums! If it weren’t for the Christianity they insist on mixing in with it, I’d be converted tomorrow.”
—Aldous Huxley (1894–1963)
“my heart leaps
in wonder.
Cold, fresh, deep, I feel the word ‘water’
spelled in my left palm.”
—Denise Levertov (b. 1923)
“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)