Motivation:

Materials:

1. One hat and one lei for every group of 4 students (or so).
2. Several apples and bananas (plastic are ok).
3. Instruction cards for the Fickle, Frustrating, and Fancy Fruit Vendors.
4. Solution handouts for Fickle and Frustrating and Fancy Fruit Vendors.
5. Overhead example finite state machine (puppy and cat).
6. Airhead 2000 exercise and/or Thimble Soda Vending machine exercise, one per student (or pair of students).
7. Airhead 2000 and Thimble Soda solutions.
8. Additional materials not yet incorporated into the lesson writeup, including design problems, exercises, transparencies, ...
9. Blank transparencies and markers.

Lesson Plan:

1. 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.
2. 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.
3. 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.
4. Repeat the previous steps, this time using the Frustrating Fruit instruction card.
5. 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.)
6. 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.
7. 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.
8. 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."
9. 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.
10. 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.
11. 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.
12. Follow this with a discussion of "why can't we get 3 apples in a row?" The diagram should make this clear.
13. 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.)
14. 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."
15. 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.



---

16. 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.
17. Next, make a list of the inputs and outputs to a puppy. Inputs: food, loud noise, petting. Outputs: drool, bark, wag.
18. 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.
19. The puppy state diagram can be found on one of your masters.
20. 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.



---

21. 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:

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:

Extensions:

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:

1. The Finite State Machine Explorer
2. " Machines that eat your words" at Mega-Math
3. 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