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)
“An individual is an encloser. Time and space, liberty and necessity, truth and thought, are left at large no longer.”
—Ralph Waldo Emerson (1803–1882)
“He hung out of the window a long while looking up and down the street. The world’s second metropolis. In the brick houses and the dingy lamplight and the voices of a group of boys kidding and quarreling on the steps of a house opposite, in the regular firm tread of a policeman, he felt a marching like soldiers, like a sidewheeler going up the Hudson under the Palisades, like an election parade, through long streets towards something tall white full of colonnades and stately. Metropolis.”
—John Dos Passos (1896–1970)
“You’d leave your own mother here, if the rules called for it.”
—Michael Wilson (1914–1978)