- A language defined by a dfa is a regular language.
- Any dfa can be regarded as a special case of an nfa.
- Any nfa can be converted to an equivalent dfa; thus, a language defined by an nfa is a regular language.
- A regular expression can be converted to an equivalent nfa; thus, a language defined by a regular expression is a regular language.
- An nfa can (with some effort!) be converted to a regular expression.

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