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)
“Weaker and weaker, the sunlight falls
In the afternoon. The proud and the strong
Have departed.
Those that are left are the unaccomplished,
The finally human,
Natives of a dwindled sphere.”
—Wallace Stevens (1879–1955)
“[I]n our country economy, letter writing is an hors d’oeuvre. It is no part of the regular routine of the day.”
—Thomas Jefferson (1743–1826)
“Trust men, and they will be true to you; treat them greatly, and they will show themselves great, though they make an exception in your favor to all their rules of trade.”
—Ralph Waldo Emerson (1803–1882)