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:
“Political image is like mixing cement. When it’s wet, you can move it around and shape it, but at some point it hardens and there’s almost nothing you can do to reshape it.”
—Walter F. Mondale (b. 1928)
“Cannon to right of them,
Cannon to left of them,
Cannon in front of them
Volleyed and thundered;”
—Alfred Tennyson (1809–1892)
“It was inspiriting to hear the regular dip of the paddles, as if they were our fins or flippers, and to realize that we were at length fairly embarked. We who had felt strangely as stage-passengers and tavern-lodgers were suddenly naturalized there and presented with the freedom of the lakes and woods.”
—Henry David Thoreau (1817–1862)
“Under the rules of a society that cannot distinguish between profit and profiteering, between money defined as necessity and money defined as luxury, murder is occasionally obligatory and always permissible.”
—Lewis H. Lapham (b. 1935)