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)
“In a room on the floor below,
Sunless, cooler—a brimming
Saucer of wax, marbly and dim—
I have lit what’s left of my life.”
—James Merrill (b. 1926)
“While you’re playing cards with a regular guy or having a bite to eat with him, he seems a peaceable, good-humoured and not entirely dense person. But just begin a conversation with him about something inedible, politics or science, for instance, and he ends up in a deadend or starts in on such an obtuse and base philosophy that you can only wave your hand and leave.”
—Anton Pavlovich Chekhov (1860–1904)
“The young break rules for fun. The old for profit.”
—Mason Cooley (b. 1927)