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 1 Like it or hate it? - Comment (1)
What are One-to-One, Onto and Bijective functions?
Posted on 21.02.2010 11:43 pm
Last fall I started learning Discrete Mathematics and I've wanted to go over a few of the more fun things that it teaches.
A lot of what Discrete Math teaches does not require a high understanding of mathematics so hopefully I'll be able to shed some light on some of these subjects.
In both math and programming, functions have a lot of properties that are fun to go over. Just a quick note about functions, for those who don't know what they are. You can think of a function as a thing that performs some action. Functions usually have some input and some output, but that is not a requirement.
A quick example of a function. You can think of the plus (+) operator in arithmetic as a function. It takes in two numbers as an input and outputs their added value, how it does that is not important for us in this entry, and how other functions work is not something we care about, they just perform magic. It's their properties that we are interested in.
A One-to-One function (or an Injective function) is when one input has a unique output. This means that if a function f has the input 3 and the output 5, usually denoted like this f(3) -> 5 then the output of that function is unique for that input. So no matter what other numbers we would put into that function, we would only get 5 with 3 as the input.
This f() of ours could be implemented like this. (Though this is not One-to-one due to overflow, but shown as an example)
int f(int x)
{
return x + 2;
}
One slight note about One-to-One functions, that it is ok not to be able to get a certain value from a One-to-One function. But in a Onto function, that is not ok.
An Onto function (or a Surjective function) is when you can create every possible output value with the input values. In this case it's ok for duplicate input values to return the same output value, but it's not ok for a function to not be able to return a value in it's domain.
An example of a surjective function is floor and ceiling functions. Their input domains could be rational numbers but the output domain could be integers.
A Bijective function is when a function is both Onto and One-to-One.
So here we have a One-to-One correspondence, where one input value correspondence to one output value, and the Onto property of being able to express every value in the domain through that function. So here a floor or ceiling function would not work, since two or more input values can express the same output value. This is often called a Perfect One-to-One correspondence.
So when you are creating your function, think about it's property, since these properties pop up in all sorts of fun places later on.
0 4 Like it or hate it? - Comment (0)
Process time: 0.017338 seconds
