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)
“O Time and Change!—with hair as gray
As was my sire’s that winter day,
How strange it seems, with so much gone
Of life and love, to still live on!
Ah, brother! only I and thou
Are left of all that circle now,—
The dear home faces whereupon
That fitful firelight paled and shone.”
—John Greenleaf Whittier (1807–1892)
“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)
“It was one of the rules which above all others made Doctr. Franklin the most amiable man in society, “never to contradict any body.””
—Thomas Jefferson (1743–1826)