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).
Programming by wishful thinking
I will not bore you with the theory, since you can read all about it in the wikipedia article, which explains the logic behind FSM better than I ever could. So I will just start with programming by wishful thinking. This is how I would like to consume an implementation of a deterministic FSM (DFSM):
1 2 3 4 5 6 7 8 9 10 11
As you can see I define the five components that make a DFSM: the states of the machine
Q, the alphabet
Sigma, the list of transitions
Delta, the start state
Q0, and the set of finish states
F. I then construct the machine by passing the components to the constructor.
I expect the upper definition to construct the FSM that is visible on the image below. As you can see the machine accepts all the words with an even number of “a” characters.
After constructing the machine we wish to test if some input is a part of the machine’s language:
1 2 3 4
I want the
Accept method to print out if the machine accepted the input or not. Also I would like to see the steps that led to the finish state if the input was accepted.
With that, I had all the specification I needed, so I started by implementing the first thing the compiler complained about: the
The transitions define how we can move between the states. So the
Transition class needs to hold the information about the
Symbol and the
EndState of the transition. Appart from that I added a
ToString() method that will be used later on.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Deterministic finite state machine
Now that we have the
Transition, we can start implementing the machine. Here is how the constructor might look like:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
I just copied the list of states and the alphabet to the internal properties, but for the other three components we need some basic validation. For the transitions we want to verify that:
- they connect the states that are defined in
- they use only symbols from
There is an additional constraint with deterministic machine and that is: each state can only have one transition for a given symbol.
Considering all the requirements this is how the
AddTransitions method might look like:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
The validations for the start state and the finish states are much simpler. We only need to check if they are defined in Q:
1 2 3 4 5 6 7 8 9 10 11 12
Accepting the inputs
That brings us to the meat of our DFSM implementation: the
Accepts method. We will need to do the following:
- read the input symbol by symbol,
- try to find a transition from the current state that uses the current symbol,
- move to the next state defined by the found transition,
- if we have read all the symbols and have ended up in one of the finish states we can accept the input,
- in all other cases (no transition possible, ending up in non finish states) we don’t accept the input.
The upper pseudo algorithm is implemented below. The main logic is in the foreach loop that reads the next symbol and tries to transition to the next state. If the transition is successful it records the current step in the steps variable. I have also added a simple
ConsoleWriter class that deals with simple print outs to the console.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
I have omitted some additional validations and the code behind the
ConsoleWriter for the sake of brevity, but the full source code can be found at GitHub.
Building the DFSM was quite fun! I have already implemented the non-deterministic one as well and will present it in one of the coming posts, and for sure I’ll do the Turing machine as well.
Before I say goodbye let me show you a test run of the DFSM on the following inputs:
1 2 3 4 5