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:
|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.|