[Syllabus] [Previous] [Next]

Grammars for Regular Languages

We already know:

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.

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.