Send
Close Add comments:
(status displays here)
Got it! This site "creationpie.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.
Finite state machines
1. Finite state machines
A
FSM (Finite State Machine) is a machine with a finite number of states and a transition table where, given the state and the transition table, the next state can be determined. A FSM has the following.
A nonempty set of states.
A nonempty set of input values.
A transition function from the current state to the next state, given an input value.
An initial state.
A set of final, or acceptance, states.
2. FSM diagrams
States can be represented using a rectangle.
3. Arrows
An arrow is used to indicate a transition from a state to another state based on an input value. A label with the arrow should indicate the input value.
4. Starting states
An arrow, without input value, into a state indicates a legal starting state.
5. Final states
An arrow, without input value, out of a state indicates a legal final state.
6. State transitions
An arrow from one state to another state on an input value indicates a legal transition.
7. Recognizing binary numbers
Here is a FSM that recognizes legal binary numbers.
The set of states is {A,B}.
The set of input values is {0,1}.
The initial state is A.
The set of final states is {B}.
The transition function is as follows.
Table of next states
Input\State A B
0 B B
1 B B
Note: Any undefined input or undefined next state is assumed to raise an error condition.
8. Finite state machine for binary numbers
Here is a
FSM = Finite State Machine that recognizes valid binary numbers.
The set of states is {Null,Odd,Even}.
The set of input values is {0,1}.
The initial state is Null.
The set of final states is {Even}.
The state is whether the binary number thus far recognized is "
odd" or "
even".
9. Table of states
The transition function is as follows.
Table of next states
Input\State Null Odd Even
0 Even Odd Even
1 Odd Even Odd
Note: It is often easier to understand the FSM if meaningful names are given to the states (e.g.,
Odd and
Even rather than
B and
C).
10. Nontrivial FSM
A FSM can become arbitrarily nontrivial such that it cannot be easily understood or diagrammed without line crossings.
An example of a nontrivial problem that can be modeled with a FSM is the elevator problem (Schach, p. 346).
11. Traffic light problem
Consider a simple traffic light. Each side can have one of three values, from top to bottom, "
Red", "
Amber", or "
Green".
12. Traffic light
A common
FSM is a (typical) traffic light. For a given traffic light there are three possible states.
"Red" on, others off.
"Amber" on, others off.
"Green" on, others off.
For most people, "
Red" means "
Stop", "
Green" means "
Go" and "
Amber" means slow for a stop as in "
Wait". For some, "
Amber" means go faster.
13. Traffic light
We will not worry about timing, only about states and transitions.
We will assume that all sides of the light have the same value.
14. Set of possible values
The set
A of possible values
A = { Red, Amber, Green }.
We are interested in two adjacent sides of the traffic light.
15. Possible states
The possible values are a subset of
A × A = {
( Red, Red ),
( Red, Amber ),
( Red, Green ),
( Amber, Red )
( Amber, Amber ),
( Amber, Green ),
( Green, Red )
( Green, Amber ),
( Green, Green ),
}
since not every state represents a valid state. For example, if both lights are green, an accident could easily occur. The ordered pairs for
A ×
B are as follows. Let us represent the above ordered pairs as follows.
RR AR GR
RA AA GA
RG AG GG
The invalid ordered pairs are
{ AA, GA, AG, GG }. Why?
The valid transitions are as follows.
GR ➡ AR
AR ➡ RR
RR ➡ GR
RG ➡ RA
RA ➡ RR
RR ➡ RG
16. End of page