I have received a question about how to approach DFSM minimization in one of the previous posts. This is an attempt to answer that question.
What is DFSM minimization?
First, let us consider what does it mean for two DFSM to be equivalent? Imagine having two DFSM that both accept the same input symbols. You then pass all the possible inputs to those two machines. If and only if the answers are the same for all the inputs then the two machines are equivalent. That is: they accept exactly the same inputs, even though their inner workings might not be the same.
This means that there are many equivalent DFSM. For example all three DFSM in the below picture accept the same input which can be written as a regular expression (0+1)*.
The three DFSM vary in the number of states and also in the number of the transitions. Nonetheless, I hope you will agree with me that they all accept the same input.
In this example case the machines are simple. But what would happen if the machines were complex - how would we determine if they are equivalent?
The answer is minimization. Minimization transforms a machine into an equivalent machine that has minimum number of states. We can then easily check if two DFSM are are equivalent. We just need to check if they have the same number of states and if all the transitions are the same.
Like I described in the previous paragraph you can use minimization to check the equivalence of the DFSM. Two other benefits (when using DFSM in programming) are:
- performance increase due to less states and transitions (faster input checking, less memory consumed),
- easier reasoning about the minimized machine since it has fewer moving parts.
Two types of states to remove
When minimizing there are two types of states that we can either completly remove or merge with other states of the machine:
- unreachable states are those states that are not reachable from the initial state of the DFA, for any input string,
- nondistinguishable states are those that cannot be distinguished from one another for any input string.
First, let us look at an algorithm for finding the unreachable states. The algorithm starts from the known reachable states which are the start states - the start states are always reachable. It then expands the list of reachable states by adding all the states that can be reached from the start states. It continues this expansion using the newly added states until it cannot add any new states to the list of reachable states. The states of the DFSM that did not end up in the list of reachable states are unreachable.
To me this algorithm feels like flooding the pipes: we have a system of pipes some of which are connected and some of which are not. We open the water and check which pipes did the water reach and which it did not reach.
Below is the algorithm in C#1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
The part of the algorithm that finds the possible transitions from the new states is quite inefficient. For each new state it tries all the symbols from
sigma. This causes us to loop over all the transitions for every symbol and every new state. A better solution is shown below. In it we are just selecting all the states that are reachable from the current state:
1 2 3 4 5
Now that we have found all the unreachable states we can remove them (along with transitions to and from them):
1 2 3 4 5 6 7 8 9 10
And now for the hard part - the nondistinguishable states. Here, we will use Brzozowski’s algorithm for minimization, which works like this:
Reversing the edges of a DFA produces a non-deterministic finite automaton (NFA) for the reversal of the original language, and converting this NFA to a DFA using the standard powerset construction (constructing only the reachable states of the converted DFA) leads to a minimal DFA for the same reversed language. Repeating this reversal operation a second time produces a minimal DFA for the original language.
To implement the described algorithm we will need the following:
- an algorithm that reverses a DFSM and produces a corresponding NDFSM,
- an algorithm for powerset construction (this algorithm converts a given NDFSM into an equivalent DFSM)
- an algorithm for detecting and removing unreachable states (see above).
Reversing a DFSM
The algorithm for reversing a DFSM is quite easy to implement and is presented below 2:
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
Putting it all together
Now that we have all the pieces we can combine them into Brzozowski’s algorithm:
1 2 3 4 5 6 7 8 9
If you check the powerset construction algorithm (or read my previous post) you can see that the implementation has the nice property that it constructs a DFSM with only reachable states. Which is why we can remove the two calls to
RemoveUnreachableStates method. The final algorithm:
1 2 3 4 5 6
And lets see how the minimization works on an example. This is how the four steps of the above minimization look like on the third DFSM from the beginning .
So this is it for minimization. The source code can be found at github.
If you read my previous article you might be wondering if those implementations will work with this reversal. The answer is no. The problem is that when we reverse a DFSM we are basically converting starting state to finish state and finish states to starting states. Which means there can be many starting states - a variant of the DFSM that my implementation does not cover. ↩
With a few minor adjustements.↩