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)
“To have friends, you know, one need only be good-natured; but when a man has no enemy left there must be something mean about him.”
—Oscar Wilde (1854–1900)
“They were regular in being gay, they learned little things that are things in being gay, they learned many little things that are things in being gay, they were gay every day, they were regular, they were gay, they were gay the same length of time every day, they were gay, they were quite regularly gay.”
—Gertrude Stein (1874–1946)
“You’d leave your own mother here, if the rules called for it.”
—Michael Wilson (1914–1978)