Sunday, May 19, 2013

Finite state machine




Example of a simple finite state machine

p = start state
a = transition
q = accept state
finite state machine consists of states, inputs and outputs. The number of states is fixed; when an input is executed, the state is changed and an output is possibly produced. Finite state machines are widely used when designing computer programs, but also have their uses in engineering, biology, linguistics and other sciences thanks to their ability to recognise sequences.
A finite state machine expressed visually is a State transition diagram. It is used to show all the states, inputs and outputs. Each state is represented with a circle, and each transition with an arrow. Transitions are labelled with an input that causes a transition and possibly an output that results from it. A double circle signifies the accept state. Not all FSMs will have an accept states and it is possible they could run for ever
A finite state machine can be with or without outputs:

Finite state automaton \

Looking at the above diagram we can see that it starts in state S1, an input of 1 will keep it in state one, and an input of 0 will move it to state S2. Once in S2 an input of 1 will keep it there, and an input of 0 will switch it back to S1. This means that the following inputs are valid:

110011001
001110011
It might appear to accept any binary value, but this isn't true. The only state it can accept in is state S1. This places the following rule on all accepted inputs: "A combination of binary digits involving an even number of zeros". This is useful for parity checks. If I try the following:
110011011
I am stuck in state S2 and the FSM has not accepted. Can you create a FSM to only accept Binary numbers with odd numbers of 1s?

No comments:

Post a Comment