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

Copyright © 1996 by David Matuszek

Last modified Feb 11, 1996