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)
“Why should the generations overlap one another at all? Why cannot we be buried as eggs in neat little cells with ten or twenty thousand pounds each wrapped round us in Bank of England notes, and wake up, as the Sphinx wasp does, to find that its papa and mamma have not only left ample provision at its elbow but have been eaten by sparrows some weeks before we began to live consciously on our own accounts?”
—Samuel Butler (1835–1902)
““I couldn’t afford to learn it,” said the Mock Turtle with a sigh. “I only took the regular course.”
“What was that?” inquired Alice.
“Reeling and Writhing, of course, to begin with,” the Mock Turtle replied; “and then the different branches of Arithmetic—Ambition, Distraction, Uglification, and Derision.”
“I never heard of ‘Uglification,’” Alice ventured to say.”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“Now for civil service reform. Legislation must be prepared and executive rules and maxims. We must limit and narrow the area of patronage. We must diminish the evils of office-seeking. We must stop interference of federal officers with elections. We must be relieved of congressional dictation as to appointments.”
—Rutherford Birchard Hayes (1822–1893)