[Overview] [Previous] [Next]

Regular Grammars

A regular grammar is either a right-linear grammar or a left-linear grammar.

To be a right-linear grammar, every production of the grammar must have one of the two forms V goes to T*V or V goes to T*.

To be a left-linear grammar, every production of the grammar must have one of the two forms V goes to VT* or V goes to T*.

You do not get to mix the two. For example, consider a grammar with the following productions:

S goes to empty string
S goes to a X
X goes to S b

This grammar is neither right-linear nor left-linear, hence it is not a regular grammar. We have no reason to suppose that the language it generates is a regular language (one that is generated by a dfa).

In fact, the grammar generates a language whose strings are of the form an timesbn times. This language cannot be recognized by a dfa. (Why not?)


Copyright 1996 by David Matuszek
Last modified Feb 11, 1996