|
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt.
This lesson and supporting materials may be copied for nonprofit
educational use only.
Motivation:
The behavior of many common items and situations can be modeled using
a simple but powerful tool called a finite state machine. This finite
state machine is not really a mechanical entity, but an abstract set
of instructions which a computer can be programmed to follow
precisely. This activity demonstrates several examples of finite
state machines.
Materials:
-
One hat and one lei for every
group of 4 students (or so).
-
Several apples and bananas
(plastic are ok).
-
Instruction cards for the
Fickle,
Frustrating, and
Fancy Fruit
Vendors.
-
Solution handouts for Fickle and
Frustrating and Fancy Fruit Vendors.
-
Overhead example finite state machine
(puppy and
cat).
-
Airhead 2000 exercise and/or
Thimble Soda Vending machine exercise,
one per student (or pair of students).
-
Airhead 2000 and
Thimble Soda solutions.
- Additional materials not yet
incorporated into the lesson writeup, including design problems, exercises,
transparencies, ...
-
Blank transparencies and markers.
Lesson Plan:
-
Start with the Fickle Fruit exercise. Each group should select a
member to be the fruit vendor (take turns). The vendor gets the
Fickle Fruit
instruction card. The other members of the group are the
fruit buyers, and they are not allowed to see the instruction
card.
-
Following the instructions on the card, the vendor dispenses fruit
depending on the requests of the other students in the group. Let
them practice making and filling fruit requests for a few minutes. It
may be more appropriate for the teacher to be the fruit vendor for the
younger students. Encourage them to keep some kind of record of the
vendor's behavior.
-
Challenge them to come up with a sequence of requests which gets them
3 apples in a row. If they get this very quickly, ask them how to get
something else. Ask them if they completely understand the behavior
of the vendor, and can predict his/her behavior.
-
Repeat the previous steps, this time using the
Frustrating
Fruit instruction card.
-
Eventually, someone will say that they can't get 3 apples in a row.
Ask if they're sure! (They can't get 3 in a row. We'll be able to
see why later.)
-
Discussion: In order to talk about the characteristics of the fruit
vendor, we need an organized way of describing his/her behavior. The
one we'll use is called a state diagram. The diagram consists of
"states," together with "transitions" which describe the way the state
changes depending on the input received. Show the children how to
diagram the first (Fickle) fruit vendor as described in the next few
steps. We've included our finite state diagrams for
fickle and frustrating fruit, and
fancy fruit for your reference.
-
In the Fickle Fruit example, the states of the vendor are: "hatted",
and "hatless." Draw circles on the board or use the overhead to show
each of these states.
-
The next thing to do is to ascertain the transitions, or the ways you
move from state to state. Ask the class what happened when the vendor
was asked for an apple while wearing a hat. (Answer: they received a
banana and the vendor took off the hat.) Draw an arrow from the
hatted state to the hatless state, and denote the transition with
"a/b" (asked for/received, or input/output), or more explicitly
"apple/banana."
-
Ask the class what other behaviors they observed. They will tell you a
list of rules corresponding to the directions on the instruction card (if
they got it right). When each rule is given, draw the appropriate arrow
in the state diagram, and label it accordingly.
-
Discussion: Tell the students that every state must have a transition for
every possible input. Ask them how many transitions there would be for
a machine with 3 states and 5 inputs (answer: 15). Point out to the
students that no uncertainty exists in the machine. All actions are
determined completely. This is why the machine is called a
"deterministic" machine.
-
Ask the students, all looking at the second
(Frustrating
Fruit) instruction
card, to construct the state diagram (solution provided at end of this
lesson). Make sure they understand the representation.
-
Follow this with a discussion of "why can't we get 3 apples in a row?"
The diagram should make this clear.
-
Now pass out the third
(Fancy Fruit)
instruction card. Play the fruit vendor
game again, but this time allow the students time to draw the state diagram
themselves while playing the game. They may need help, since they don't
know all the states right away. Tell them that is ok, they can add states
as they observe them (Hat and Lei, Hat and no Lei, etc.)
-
Discuss the state diagram for the Fancy Fruit
Vendor. An important point to note is that even though "hatted
with lei," and "hatless without lei" seem like different states, they
are really the same since their outgoing transitions are all the same.
We say that the two states are "redundant," and we collapse them into
a single state encompassing both situations: "hatted with lei OR
hatless without lei."
-
Discussion: Explain that the exercise they've been doing, building a machine
by watching a system's behavior, is called inference. It's also true that
such inference is nearly impossible when the state of the system cannot
be seen. For example, if the students could not see the vendor removing
and replacing the hat, they would have a hard time determining what fruit
they would be given when they asked for a banana.
-
Now it's time to start designing our own machines from scratch. Tell
the students that you will model the behavior of a
puppy. Do the
development in stages so the students learn to organize their
thoughts. The first step is to write down the states: sleeping,
eating, playing.
-
Next, make a list of the inputs and outputs to a puppy. Inputs: food, loud
noise, petting. Outputs: drool, bark, wag.
-
Finally, put in the transitions. To do this, look at one state at a time,
and decide what happens for each input. For example, if the puppy is eating,
we would need to decide what happens when it is given food. Then we need
to decide what happens when it hears a loud noise. And finally we need
to decide what happens when it gets pet.
-
The puppy
state diagram can be found on one of your masters.
-
You may want to discuss with the students some other, similar state
diagrams they might make, like a baby, or a
cat. Cats only
have one state -- aloof. Give the students time to suggest machines
which might be modeled using state diagrams.
-
A possible final project for this lesson would be to give students a
vague (or not so vague) specification of a real object, and have each
team of 2 or 3 design a finite state machine that models the object.
Refer to either the
Airhead 2000 (easier), or the
Thimble Soda
(harder) project. The process of deciding on states can be difficult,
and often requires intuition that comes from experience. Be prepared
with some good hints. Other ideas include modeling the behavior of
the different settings-modes of a fancy digital watch, or modeling a
"giga-pet". (For the giga-pet, to simplify things assume that the
device doesn't change with the passing of time, but only upon user
input.)
Conclusion:
One common application for finite state machines is searching for words
or strings in a word processor. A web search engine may use such a machine
as well. Here's an example of a simple string matching machine. The machine
stops with a "success" when any string of letters (a word for example)
ends in "baby." Take an input word, such as "baobab," and look at
one letter at a time from left to right. The first "b" moves you
to the first state, and then the "a" to the second state, and then the
"o" returns you to the start. You end up in state 3 after the final
"bab." This word doesn't result in "success" since it doesn't end
in the stop state. Try running the input "bababy" through the machine
to see what happens. Notice that if the arrow labeled "a" from the fourth
state pointed back to the beginning, the machine would not have found the
match "baby" in the sequence "bababy."
(Note that "*" means "everything else.")
For more information and
activities suitable for kids, see the
"machines that eat your words" page of the
Mega-Math site, or
the fun Treasure-Island activity in
Computer Science Unplugged,
which is also related to our lesson on
graph search.
Evaluation:
For younger children, simply observe the diagrams they create for Frustrating
or Fancy Fruit. Even the youngest children should be able to complete
the Frustrating Fruit diagram. More advanced students will enjoy
the challenge of creating a machine from the problems described in the
Airhead 2000 or Thimble Soda handouts. Develop a simple 4 or 5 point
rubric to use in assessing the students' work.
Extensions:
Finite state machines can be used to decode messages encoded using a
Huffman code. (We discuss Huffman coding in the
text compression lesson.) Have
students design a machine to accomplish the decoding for a given code.
Will a finite state machine work for decoding any code? Why or why
not? (Answer: It will not work for every possible code. There are
unambiguous variable length codes which are not prefix codes. You
need a different type of machine to decode these codes.)
Use finite state machines to describe the behavior of a cheap
digital watch with two buttons. Use them to learn how to set the
clock on the VCR.
There is a vast literature on finite state machines, accessible
from middle elementary on up. Look for books with titles including
"Theory of Computation" in them. Also, there are finite state machine
simulators available on the web. (See "Related Links" below.)
Related Links:
-
The Finite State Machine Explorer
- "
Machines that eat your words" at
Mega-Math
- Treasure-Island activity in
Computer Science Unplugged
(also related to our lesson on
graph search).
Standards:
-
NCTM K-4: 1, 2, 3, 4, 13.
-
NCTM 5-8: 1, 2, 3, 4, 8.
-
NCTM 9-12: 1, 2, 3, 4, 12.
Skills:
- Problem solving / reasoning / communication / connections
- Logical thinking
- Process modeling
Copyright (c) 1998, C. Heeren, T. Magliery, and L. Pitt.
This lesson and supporting materials may be copied for nonprofit educational
use only.
|