Simple State Machines
Posted on 03.03.2010 09:23 pm
Another Discrete math topic that I found to be fun and sometimes challenging is the topic of state machines. State machines are used to describe possible states in a machine and what transitions it can make from each state.
State machines are usually depicted with either state transition tables or state diagrams, and here I will focus on the diagrams, since they help in understanding the topic better.
Let's just start with a simple machine that everybody can understand (specially programmers). A vending machine.
Lets say that this machine only has one item to sell, that it costs 20 moneys and you can't get a refund and the coins it accepts are 5 and 10 money coins (just to simplify the machine even further).
Here we have four states. The machine starts in state A, if it receives a 5 money coin, it proceeds to state B, but if it receives a 10 money coin, then we go to state C. When we are at state C or D, it is possible to get our product. If we are in state C and get a 10 as an input, then we proceed to state A and call some function V (vend).
If you notice that every state has two outputs possible, because it accepts two coins as input and it needs to be able to handle when any coin is used at any time. You can also notice that this machine cheats you out of your money if you are in state D and put in a 10 coin, that bastard.
This example is often used to introduce students to a state machines but you should note that this is only one type of a state machine, there are many others.
State machines are often used to output data based on the input, a fun example is a state machine that reads in a binary string and flips every other bit. So for example, this machine would read 1001 and output 1100.
These machines are called Mealy machines.
This machine can be implemented in pretty simple code.
void binary_flip(char* c)
{
char state = 'A';
for(int i = 0; c[i]; i++)
{
switch(state)
{
case 'A':
state = 'B';
if(c[i] == '1')
{
cout << '1';
}
if(c[i] == '0')
{
cout << '0';
}
break;
case 'B':
state = 'A';
if(c[i] == '1')
{
cout << '0';
}
if(c[i] == '0')
{
cout << '1';
}
break;
}
}
}
0 2 Like it or hate it? - Comment (1)
G i $ l i
0 1 / Posted on 10.03.2010 12:22 am
static void BinarySwitch(char[] chars){
for (int i = 0; i < chars.Length; i++)
{
// i % 2 == 0 is state A
// i % 2 == 1 is state B
if (i % 2 == 1)
Console.WriteLine((int.Parse(chars[i]) - 1) * -1);
else
Console.WriteLine(chars[i]);
}
}
Process time: 0.006057 seconds
