Besides eliminating useless states that do not contribute to word acceptance, what else can we do to “clean up” an automaton? In other words, we would like to reduce the number of states in an automaton to as small as possible without affecting its power of accepting words.
The next thing we can do is to look to find states that do the same thing and combine them into one state. Two states do the same thing if, acting as starting states, when an arbitrary word is fed into the automaton, they lead to the same conclusion: either both accept the word, or both reject it. Arbitrary automata are too general to ensure definite conclusions, so we restrict our attention to deterministic finite automata.
Definition. Let be an automaton with a single start state . For any state , define to be the automaton obtained from by replacing by . In other words, . Two states are said to be indistinguishable if .
If is a DFA, is the same as saying that, for all words over , iff . For the following discussion, we shall assume that is a DFA, unless otherwise specified.
Here are two basic observations:
if , then : Let and . Given any over , we have that , which is in iff is in . Hence .
if and , then : as shows that . As a result of this, iff .
Define as follows: , , , and , for any .
This can be proved by induction on the length of :
suppose , then for any ,
It also has the property that for if two states are indistinguishable, they are in fact the same state: suppose , then for every over , iff , or iff , which is the same as saying iff , or , or .
Definition. An finite automaton with a single start state is said to be reduced or minimal if implies , where is the indistinguishable relation on its state set.
Thus constructed above is reduced.
Note that , as , and are combined into one state . Similarly, , as , and are combined into . Finally, note that .
With respect to DFA’s, the following is true:
We have already shown that given a DFA , the automaton constructed above is reduced. Next, we see that iff iff iff iff . Therefore, .
Next, suppose is accessible, we want to show that is accessible for any . Since is accessible, for some word over . So is accessible as well. This proves that is accessible.
Suppose now that is simplified. Pick any , we want to show that is useful. Since is useful, there are words over such that and , or equivalently and , so that is useful. This shows that is simplified.
Remark. The proposition above is not true in general for non-deterministic finite automata: two equivalent simplified reduced NDFA may not be isomorphic. However, there exist reduction techniques for NDFA such that the reduced automata produced using these techniques are unique up to isomorphism.
|Date of creation||2013-03-22 19:01:56|
|Last modified on||2013-03-22 19:01:56|
|Last modified by||CWoo (3771)|