Given any dfa M, application of the procedure reduce yields another dfa such
that
L(M)= L( ).
Furthermore, is minimal in the sense that there is no other dfa with a smaller
number of states that also accepts L(M).
Proof: There are two parts. The first is to show that the dfa created by reduce is
equivalent to the original dfa. This is relatively easy and we can use inductive
arguments similar to those used in establishing the equivalence of dfa's and nfa's.
All we have to do is to show that δ * (q i ,w) = q j if and only if the label of
is of the form…j.…We will leave this as an exercise.
The second part, to show that is minimal, is harder. Suppose has states
{p 0 ,p 1 ,p 2 ,…,p m }, with p 0 the initial state. Assume that there is an equivalent dfa
M 1 , with transition function δ 1 and initial state q 0 , equivalent to , but with
fewer states. Since there are no inaccessible states in , there must be distinct
strings w 1 ,w 2 ,…,w m such that
But since M 1 has fewer states than there must be at least two of these strings,
say w k and w l , such that
Since p k and p l are distinguishable, there must be some string x such that
is a final state, and
is a nonfinal
state (or vice versa). In other words,w k x is accepted by and w 1 x is not. But
note that
that
L(M)= L( ).
Furthermore, is minimal in the sense that there is no other dfa with a smaller
number of states that also accepts L(M).
Proof: There are two parts. The first is to show that the dfa created by reduce is
equivalent to the original dfa. This is relatively easy and we can use inductive
arguments similar to those used in establishing the equivalence of dfa's and nfa's.
All we have to do is to show that δ * (q i ,w) = q j if and only if the label of
is of the form…j.…We will leave this as an exercise.
The second part, to show that is minimal, is harder. Suppose has states
{p 0 ,p 1 ,p 2 ,…,p m }, with p 0 the initial state. Assume that there is an equivalent dfa
M 1 , with transition function δ 1 and initial state q 0 , equivalent to , but with
fewer states. Since there are no inaccessible states in , there must be distinct
strings w 1 ,w 2 ,…,w m such that
But since M 1 has fewer states than there must be at least two of these strings,
say w k and w l , such that
Since p k and p l are distinguishable, there must be some string x such that
is a final state, and
is a nonfinal
state (or vice versa). In other words,w k x is accepted by and w 1 x is not. But
note that