Date: Wed, 08 Jan 1997 20:38:01 GMT Server: NCSA/1.4.2 Content-type: text/html
We can construct a DFA where
is given by the table (using the subset construction):
and where
and
.
First, we make a new start state that has no incoming arcs:
Next, make a new final state with no outgoing arcs:
Eliminate a state. The state looks like a good candidate:
Eliminate state :
Eliminate :
Accounting for the final start state, the equivalent regular expression is
. This can be simplified to
.
We will show that accepts
with the following behavioral lemma:
Behavioral Lemma: For all ,
if and only if
.
Given that this lemma is true, we can prove that .
Suppose
and
. Let x = ay for
and
. Note that
. It follows that:
Suppose that and
. Again, let x=ay:
Consider when :
Combining these observations, we have , and so
there is an NFA that accepts
.
Thus, if L is regular,
is regular.