A regular language is given in a standard representation
if it is specified by one of:
(The importance of these particular representations is simply
that they are precise and unambiguous; thus, we can prove
things about languages when they are expressed in a standard
- A finite automaton (dfa or nfa).
- A regular expression.
- A regular grammar.
Membership. If L is a language on alphabet ,
L is in a standard representation, and w
*, then there is an
algorithm for determining whether w
Proof. Build the automation and use it to test w.
Finiteness. If language L is specified by a standard
representation, there is an algorithm to determine whether
the set L is empty, finite, or infinite.
Proof. Build the automaton.
Equivalence. If languages L1 and L2
are each given in a standard representation, then there is an
algorithm to determine whether the languages are identical.
- If there is no path from the initial state to a final
state, then the language is empty (and finite).
- If there is a path containing a cycle from the initial
state to some final state, then the language is infinite.
- If no path from the initial state to a final state contains
a cycle, then the language is finite.
Proof. Construct the language
If this language is empty, then L1 = L2.
Copyright © 1996 by David Matuszek
Last modified Feb 24, 1996