VT*
VT*
T*
That is, the left-hand side must consist of a single variable, and the right-hand side consists of an optional single variable followed by any number of terminals. This is just like a right-linear grammar except that, following the arrow, a variable can occur only on the left of the terminals, rather than only on the right.
We won't pay much attention to left-linear grammars, because they turn out to be equivalent to right-linear grammars. Given a left-linear grammar for language L, we can construct a right-linear grammar for the same language, as follows:
| Step | Method |
|---|---|
Construct a right-linear grammar for the (different) language L .
|
Replace each production A
x of L with a production A
x, and
replace each production A
B x with a production A
x B.
|
| Construct an nfa for L
from the right-linear grammar. This nfa should have just one final state.
|
We talked about deriving an nfa from a right-linear grammar on an
earlier page. If the nfa has more than one final state, we can make
those states nonfinal, add a new final state, and put 
transitions from each previously final state to the new final state. |
| Reverse the nfa for L
to obtain an nfa for L. |
1. Construct an nfa to recognize language L. 2. Ensure the nfa has only a single final state. 3. Reverse the direction of the arcs. 4. Make the initial state final and the final state initial. |
| Construct a right-linear grammar for L from the nfa for L. | This is the technique we just talked about on an earlier page. |