Learning Finite State Machines

Copyright (c) 2000 Lion Kimbro. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with no Invariant Sections, with no Front-Cover Texts, and with no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License".

Overview

The goal of this guide is to teach you about Finite State Machines. After you are done reading it, you should be able to...

1. Understand What States and Transitions Are
2. Use a Finite State Machine
3. Draw State Diagrams
4. Program Finite State Machines
5. Create Transition Tables
6. Use Transition Tables
7. Program Finite State Machines with Transition Tables

...and understand the following words...:

1. State
2. Transition
3. Alphabet
4. Acceptor State
5. Recognizer

This document is made to be printed, written on, and stored so that you can look back upon your work later..! Do so to gain maximum benefit from this guide.

What is a Finite State Machine?

Finite state machines are machines that "transition" between a finite number of "states".

Here is a diagram of a finite state machine:

Finite state machines consist of four basic elements:

• States
• A Start State
• An Alphabet
• Transitions

States

The states on this diagram are A, B, C, D, and E.

States represent the possible "states" the machine can be in. A Finite State Machine is in only one state, called the "current state", at a given time.

Finite state machines keep track of where they are, not where they have been.

Start State

The start state is the state that the Finite State Machine begins in. The start state is state "A", in the example above.

Alphabet

The alphabet is the collection (or "set") of symbols that serve as inputs to the Finite State Machine.

The numbers "1" and "2" are the alphabet in this example.

Transitions

Transitions move the machine from state to state, depending on the input (which is a member of the alphabet) and the current state (which is a member of the states).

In diagrams, transitions are represented by arrows. Formally, transitions are represented by a function of the current state and the input. The table above depicts the transition function.

Examples

[Examples: A AI in a game, a word acceptor.]

Exercise

Read what MegaMathematics has to say about Finite State Machines. This link includes pictures.

Read a formal definition of finite state machines.

Draw State Diagrams

The goal here is to make sure that you can draw state diagrams.

The Phases of Water

We're going to make a finite state machine for water that will have three states:

• Ice
• Water
• Steam

Draw the states here:

Here's the drawing Pico made:

(It says vapor rather than steam because the version of this document he used said vapor, not steam.)

If your drawing looks somewhat similar to that, you're doing fine.

Generally, we like to put the names of the states within circles because we're going to start drawing lines between the circles soon, and we don't want those lines to cross over the words and make them unreadable.

Now, draw the states again, but include the transitions between the states this time. The transitions will be "Heat" and "Cool".

Be sure to draw the following things:

• States
• Transitions
• Arrows on your Transitions - we need to be able to tell which way they go.

Here's the drawing Pico made:

It doesn't have to be pretty.

Pico's drawing is correct. There are 4 transitions (arrows) here:

• Ice turns into water when heated.
• Water turns into ice when cooled.
• Water turns into steam when heated.
• Steam turns into water when cooled.

Here's my drawing:

I like this drawing better because it places emphasis on the progressive ordering of the phase changes.

Is there anything missing? What happens when we heat steam or cool ice? We didn't talk about it, but if you'd like to add it to your diagram, you can add the following transitions:

• Steam that is heated remains steam.
• Ice that is cooled remains ice.

Congratulations. I hope that you have learned how to draw state diagrams. If not, mail me at lion@speakeasy.org.

Use State Diagrams

Great! Now, lets pretend that we had a piece of ice. Put your pen on the ice state. Now, trace out the following transitions: [heat] [heat] [cool] [heat] [cool] [cool] [heat] [cool] [heat] [heat] [cool] [heat]

The pen should be on "steam" when you finish. If not, go back and make sure that you have everything allright.

This is a pretty lame example, since all we're doing is counting. For example, we could call ice "zero" (0), call water "one" (1), and call steam "two" (2). The [heat] transition is just adding 1, and the [cool] transition is just subtracting 1.

Count up the number of heats, and put the result here:

Count up the number of cools, and put the result here:

You should have gotten 7 and 5. If we +7 and -5, we get +2. Since we started on ice (0), we +2 and end up on steam (2).

Here are two questions for you that I don't have time to answer right now:

Would the same result have been had if we started at 1? Write your thoughts here:

Is this a good representation of phase transitions? Why? Write your thoughts here:

Lets make a more interesting state diagram. (too be written)

Program Finite State Machines

Create Transition Tables

Use Transition Tables

Program Finite State Machines with Transition Tables

Resources

• Zeroes and Ones::State Machines - an article on AI programming. Read the section on State Machines, and the section on Enumeration Types. Side note: His section on the game industry is quite accurate.
• The Finite State Machine Explorer - a FSM Java applet, that lets you create states, and check to see if an input is accepted by a finite state machine. This obeys the formal definition of a FSM, with a start state, acceptor states, states, and transitions. Unfortunately, it takes a little while to load.
• A Formal Definition of Finite State Machines.
• Ramblings on FSAs in Computer Science - how to turn an NFA (Nondeterministic FSA) into a DFA (Deterministic FSA)
• Minimization of Finite State Machines - A very mathematically formal description of how to minimize a finite state machine.
• Mathmania, perhaps my favorite math site on the web, has a colorful tutorial on Finite State Machines. It also has sections on graphs, knots, and sorting networks.
• Finite State Machine Exercises from Tom 7
• Hierarchical State Machine
• Finite-State Machines - An excellent introductory page on Finite State Machines. It gives the examples of a soda machine, an ATM machine, and language processing. It focuses mostly on text processing, and goes in depth, showing how to use switch statements to build a finite state machine in C.

GNU Free Documentation License

I have linked to a local copy of the GNU Free Documentation License.