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)
“Therefore when thou doest thine alms, do not sound a trumpet before thee, as the hypocrites do in the synagogues and in the streets, that they may have glory of men. Verily I say unto you, they have their reward. But when thou doest alms, let not thy left hand know what thy right hand doeth.”
—Bible: New Testament Matthew 6:2-3.
The Sermon on the Mount.
“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)
“You’d leave your own mother here, if the rules called for it.”
—Michael Wilson (1914–1978)