# Deterministic Finite State Machine Minimization

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.

# Powerset Construction in C#

In the last two articles I have implemented the deterministic finite state machine (DFSM) and the non-deterministic finite state machine (NDFSM). As you probably all know the two variants are equivalent in terms of power; that is everything that can be expressed with one can also be expressed with the other. This may come as a surprise when you first hear about it, but you are soon presented with the powerset construction which converts a NDFSM into a DFSM and thus proves one part of the equivalence. The other part is trivial since DFSM is only a limited NDFSM.

# Non-deterministic Finite State Machine Implementation in C#

Last time I implemented the deterministic finite state machine (DFSM). This time I will do the same for the non-deterministic (NDFSM) one. I chose the variation without the `epsilon` transitions and will leave that for exercise if someone might find it intriguing.

The only difference between the DFSM and NDFSM is that while the DFSM can only have a single transition for a given state and input symbol the NDFSM is not limited in that regard. It can have multiple transitions for a given state and input symbol.

# Deterministic Finite State Machine Implementation in C#

While I was working at the Faculty of Computer and Information Science I have implemented many of the standard algorithms from the famous Cormen’s Introduction to Algorithms. Since I was a part of the Laboratory for algorithms and data structures that is to be expected. However, I have never implemented many of the great results from the Theory of Computation.

This is why I decided to implement the finite state machine and the Turing machine in C# as an exercise. In this blog post I will start with the easier of the two, the finite state machine (FSM). 