Students act out the operation of a finite state
machine that has been drawn with masking tape on the classroom floor.
Students receive (or make) tickets that serve as inputs to the machine.
The tickets tell them which lines on the floor to follow and which circles
or states to pass through. If they end up in an
accept state they receive a prize. This
means that what was printed on their ticket was recognized by the machine
as a word in its language .
Finite State Machine drawn on the floor as described below.
For each student:
Several strips of paper, approximately 2" X 8".
Pencils, pens, or markers for writing.
A large quantity of small prizes, at least 2 or 3 per student.
Preparation and Set-Up
Draw a large copy of a finite state machine on the classroom floor with
masking tape.
is a good one to
begin with.
A smaller and simpler machine that might be more appropriate
for very young or inexperienced students is
The resting places to which the arrows point should be large enough for one child to stand in. They can be drawn as circles or squares.
Place the prize containers in or alongside the circle which has the large
dots inside. This is the circle for the accept state.
The labels a,
b, etc. can be written on pieces of paper and taped alongside the
lines.
Be sure to include the arrow heads that are on the lines in the
drawing as well.
Use an area of the floor that is large enough for the
children to gather in a circle around the drawing and be able to see what
is happeneing. It is ideal if this is an area that will not need to be
covered with furniture as soon as the activity is finished so that the
drawing can remain on the floor for several days. It is also interesting to use an area that receives public use, such as the hallway or a corner of the gym or cafeteria, as this gives other students a chance to speculate about what a finite state machine is, and the students who are "in the know" have a chance to demonstrate how it works.
For very young students who have difficulty
recognizing and distinguishing among letters, you can use colored
dots or pictures of familiar objects in place of the letters
throughout the activity. If colored dots are used, children could
construct their input tickets by connecting strings of colored
unifix cubes.
Tell the students that the diagram on the floor is what computer
scientists call a finite state machine .
This machine has a language
of its very own. It's kind of a silly language by our standards. It
doesn't have sentences, just words, and the only letters it uses to
make it's words are a and b . The language that we
speak can't make very many words
with just a and b in them, but the words
in the language of
this Finite State Machine are different from our a and b
words. Many different combinations of a's and b's are words in the language of the Finite State Machine.
When
you come to the machine with a word, the machine can check to see if
the word is in it's language. If it's not, the machine isn't really
very interested in you. But if you bring the machine a word that is
in it's language, it accepts that word and you win a prize.
Have each student take a strip of
paper and write down a word made up of a's and b's. Then they will be able to
to test to see if their word is in the machine's language. There are two
important things to remember while doing this:
First, the machine only understands words that are
made up of the letters a and b . If you use any
other letters, the machine won't understand them for sure.
Secondly, the machine doesn't follow rules that we have
about spelling, so a word like babb or baaaabb might
work--even though these don't make much sense as English words.
It is best when just starting to use words that are no longer than 8 letters.
For the first round you may want to supply students
with words to try, and then let students make up their own words
afterwards.
Invite a student to try a word by walking through the machine. Have
the student read off the letters in the word to the other students.
Here is how a word is tested in the machine:
The student holds the ticket with the word on it and stands in the circle marked Start or S. Ask,
"What is the first letter of your word?" Show the student how to
walk down the line that is marked with that letter and stop in the
next circle.
Then ask, "What is the next letter of your word?"
Again, the student must walk down the line labeled with that letter
and stop in the next circle.
The student continues in this manner
until the end of the word on the ticket is reached.
Ask the other members of the class to note where the student has
ended up. Is the student in the circle where the prize bucket is?
That circle is called the accept state .
If the student
has landed in the accept state when the word is all finished, then
we know that this word is in the machine's language , and the student
receives a prize. If it isn't, the student wins no prize. In
either case, the student can write down a new word to try next time.
Note that if the student happens to pass through the
accept
state (the circle with the prizes) before getting to the last letter
of the word on the paper, this does not count as having the word
accepted. The word is accepted only when the student lands in the
accept state after processing the last letter of the word.
Invite a few more volunteers to walk through the machine slowly
with their tickets in hand. When all of the students understand what
to do, they can begin walking though the machine more quickly.
Allow each student to try several words. When students catch
on to how to make a winning word, suggest
that they try making
a word that is very long--a dozen letters, or even more.
Have students keep playing until everyone catches on to how to put
together words that will win a prize.
Students can think about and discuss the following questions:
How do you know where to go next?
When do you get to take a prize?
If I use a word like aaba, I pass the place where
the prizes are stored, but I can't have one. Why?
Without actually walking on the machine, tell me if these words
will be accepted: aabb, abbaab, abbbaab, or
bbaaa. (These examples assume you have used
. If you have used a
different finite state machine, you will need other examples, of course.)
How can you figure out whether a word will work without actually walking through the machine?
Make two columns on the board and labeled Accepted and
Not Accepted. List words that the students tried in the
appropriate
columns. There is a shorthand notation for writing down words so that they don't have to be unnecessarily long. One aspect of this notation which will probably be useful at this point is:
The chart above may resemble the lists of words that did and did not accept. Here are some things to consider after you have tried out a series of words and listed whether they were accepted or not:
What strategies did you use to think up words to try?
Look for patterns in the words in the two lists. Make a new list labeled
Patterns and list the patterns that the students describe.
Help students to
continue referring to the machine as well as the lists of words when
they talk about patterns. Have all the students agree on the
description and the wording of the patterns as they are written down.
If agreement can't be quickly reached for a statement, put question
marks by it as reminder to think about it some more and return to
it later.
How does understanding patterns in the words that are accepted
help you to think up more words that will be accepted?
There is a simple, but powerful notation for writing down the words of a finite state machine's language. For the following discussion, as you choose words to use for examples, use as many words as possible that were on the students' list of accepted words.
The following words are all in the language of this finite state machine: . What else do they all have in common? (Hint: Look for patterns in the letters.)
abab
abbab
abbbbbab
abbbbbbbbbbbbbbbbbbbbbbab
We could think of hundreds of words that follow the same
pattern that is in these words. If we want to talk about all of
them, we can write: ab*ab.
The * after the first b means, "Put in as many
b's as you
want. It won't change the results." (This even means that the result doesn't change if you put in zero
b's.)
If you look at the finite state machine itself, you can see that ab*ab represents many words in the language of Machine 1.
Can you write a different expression for Machine 1's winning words that has a
* in it? Collect examples from students and write them down.
Help the students to verify (by looking at the finite state machine) that these are words that will be accepted.
Sometimes part of a word repeats a string or
sequence of letters over and over
again.
for example, accepts of all the following words:
aaab
aaabaaab
aaabaaabaaab
You can show this by writing (aaab)*. The * means that something is repeated, and the parentheses are
used to show that you repeat the string aaab, and not just the b preceding the *.
An even shorter way to write (aaab)* is:
Can you
explain what all the parts of this expression mean?
After the discussion, give students time to experiment some more with the
finite state machine on the floor. If it is well-understood by all
students, the activity could be modified in any of the following ways:
Repeat the activity with a different finite state machine. For a machine that whose alphabet consists of three letters instead of two, you can use:
As you continue to experiment with finite state machines,
you may want to move to a larger area, such as a gym or
multipurpose room so that you can
draw new finite state machines on the floor. You
can also photocopy diagrams of a finite state machine and let the
students work with them individually or in groups. Markers such as
finite state
machine unifix cubes, poker chips, or beans can be used to show the
how the player moves on the paper.
Students can draw their own finite state machines and experiment
to find which words will be accepted and which ones won't.
Decide how many states or circles that your finite state machine will have, and draw them on the page.
Put a large S inside the circle which you want to be the starting state.
Color in the circle which you want to use for the accept state.
Decide how many letters you want the alphabet of your finite state machine to have, and decide what those letters will be. (They can be letters of our alphabet, or any other unique symbol. )
Draw an arrow from
each state (or circle) to show the path that should be followed for each letter of your machine's alphabet. For example, if your machine's alphabet will have three letters, each state or circle in your machine will have three arrows leaving it, and each arrow will be labeled with a different letter of the machine's alphabet. The arrows can be drawn to any other state (circle), including back to the state (circle) that the arrow started from.
There are no restrictions on the number of arrows that can be coming into a state (or circle), but (as explained above) each state (or circle) will have exactly as many arrows leaving it as there are letters of its alphabet.
Notice that the inputs aaab and bab will both be accepted by
.
Whether you start out with aa or b, if the rest of the word is ab you will have a winning ticket. Verify this by looking at the finite state machine.
In the shortcut notation, you can show this by writing (aa + b)ab. The +
means "Pick one
of these, but not both." Trace the route you would follow with each of the tickets, aaab and bab and explore how this aspect of the notation is works. Why is it useful?
With the addition of this final element,
we have built a notation system which allows us to look at a finite state machine, and then write down an expression that describes all the tickets that will win as inputs to that machine.
Such an expression is
called a regular expression .
Take a look at a simple example, that uses
. If you only consider tickets whose input it long enough for the person to arrive at the accept state (and not go beyond it), the machine could be described by the expression:
(ab*a) + (ba*b) . Experiment with this, look at the finite state machine, and verify that it is true.
What would you have to add to this regular expression to take into account every possible input? It's not difficult to figure out, you just have to keep all the possibilities straight! (There is more than one regular expression that is correct, too.)
The regular expression that takes into account every possibility for
is (aba* + b)(aa*b + b)(ab*a(aa*b + b))* .
Experiment with writing regular expressions for other finite state machines. If the whole, perfect regular expression seems too huge and difficult to draw, start with a regular expression that describes one part of the finite state machine and see what you can add to it.
Try to draw a finite state machine for which the regular expression will be very, very simple.
The finite state machine gets its name because it has a
finite number of states (circles).
Even if there are very many of them, you
can count them, and you can say exactly how many there are. The same
thing is true for the number of letters in its alphabet .
Can you see why Machine 1 will accept an infinite number of words?
We could work for a long time, get very tired, and still never finish
the rather silly task of completing just this part of the list of
words that this machine will accept:
ababb
abaabb
abaaabb
abaaaabb
...etc.
Not only that, but there is an infinite number of inputs that you can
invent that the machine is sure to reject!
Materials 
is a good one to
begin with. 
Can you
explain what all the parts of this expression mean?
