[Overview] [Previous] [Next]

Grammars for Regular Languages

We already know: So dfas, nfas, and regular expressions are all "equivalent," in the sense that any language you define with one of these could be defined by the others as well.

We also know that languages can be defined by grammars. Now we will begin to classify grammars; and the first kinds of grammars we will look at are the regular grammars. As you might expect, regular grammars will turn out to be equivalent to dfas, nfas, and regular expressions.

Copyright © 1996 by David Matuszek
Last modified Feb 11, 1996