[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.
- 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
- An nfa can (with some effort!) be converted to a regular
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