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)
“The Christian ideal has not been tried and found wanting. It has been found difficult; and left untried.”
—Gilbert Keith Chesterton (1874–1936)
“[I]n our country economy, letter writing is an hors d’oeuvre. It is no part of the regular routine of the day.”
—Thomas Jefferson (1743–1826)
“Each person calls barbarism whatever is not his or her own practice.... We may call Cannibals barbarians, in respect to the rules of reason, but not in respect to ourselves, who surpass them in every kind of barbarity.”
—Michel de Montaigne (1533–1592)