Regular Grammar - Mixing Left and Right Regular Rules

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)

    “And then he would lift this finest
    of furniture to his big left shoulder
    and tuck it in and draw the bow
    so carefully as to make the music

    almost visible on the air.”
    —Stanley Plumly (b. 1939)

    “A regular council was held with the Indians, who had come in on their ponies, and speeches were made on both sides through an interpreter, quite in the described mode,—the Indians, as usual, having the advantage in point of truth and earnestness, and therefore of eloquence. The most prominent chief was named Little Crow. They were quite dissatisfied with the white man’s treatment of them, and probably have reason to be so.”
    —Henry David Thoreau (1817–1862)

    “The only rules comedy can tolerate are those of taste, and the only limitations those of libel.”
    —James Thurber (1894–1961)