[Overview] [Previous] [Next]

Left-Linear Grammars

In a left-linear grammar, all productions have one of the two forms:
V goes to VT*
or
V goes to 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 Lsuperscript R. Replace each production A goes to x of L with a production A goes to xsuperscript R, and replace each production A goes to B x with a production A goes to xsuperscript R B.
Construct an nfa for Lsuperscript R 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 empty string transitions from each previously final state to the new final state.
Reverse the nfa for Lsuperscript R 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.


Copyright 1996 by David Matuszek
Last modified Feb 11, 1996