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:
“How natural that the errors of the ancient should be handed down and, mixing with the principles and system which Christ taught, give to us an adulterated Christianity.”
—Olympia Brown (1835–1900)
“Can anything be so elegant as to have few wants and to serve them one’s self, so as to have somewhat left to give, instead of being always prompt to grab?”
—Ralph Waldo Emerson (1803–1882)
“[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)
“Playing games with agreed upon rules helps children learn to live by rules, establish the delicate balance between competition and cooperation, between fair play and justice and exploitation and abuse of these for personal gain. It helps them learn to manage the warmth of winning and the hurt of losing; it helps them to believe that there will be another chance to win the next time.”
—James P. Comer (20th century)