Finite state automata (FSAs) sound complicated, but the basic idea is as simple as drawing a map.
This fun activity is based around a fictitious pirate story which leads to the unlikely topic of reasoning about patterns in sequences of characters
National Center for Women & Information Technology (NCWIT) has a learning package called Unplugged in a Box which has detailed lesson plan of the "Treasure Hunt" activity.
Mordechai (Moti) Ben-Ari from the Weizmann Institute of Science, Israel has programmed the Finite State Automata Unplugged activity in Scratch which can be downloaded in a zip file of the complete set of activities . Please read the ReadMe.txt for documentation.
The Greenroom resources area using the Greenfoot software has the treasure finding finite state automata exercise you can download and use in the Greenfoot environment. If you are a teacher, you can apply easily to join and use the resources there.
An older version of this activity can be downloaded in PDF format here. The content is similar to the current version, but there's some extra technical information.
The Mathmaniacs web site has a similar activity (lesson 5), and a related one (lesson 6)
SwissEduc has a programming environment called Kara (requires Java installed), which is a programmable ladybird robot that has been developed to help teach Computer Science concepts such as finite state machines, turing machines. The variations of this program are given below:
Merchant Taylors' School UK in it's free course on Moodle aimed at AS Computing has an activity in Finite State Machines based on Kara . Read also their Getting Started with Kara guide.
jayisgames has a game made in Flash that teaches the concept of Finite State Automata called Manufactoria.
many thanks!
I've been running a 2 week tech camp (http://xktechcamp.blogspot.com/) for 4th thru 6th graders with my 8th grade son as my assistant. These unplugged activities have been such a fun way to explain CS concepts all while taking a break from the screens (which we really needed). My son took this treasure hunt activity and put his own twist on it.
Science Night Activity with constructed islands
We adapted this activity for the Berlin Long Night of Science 2010. Families come to the universities to see what it is that we do with their tax money. Computing stuff seems rather boring, so we decided to use the Finite State Automata game. I've used it in computing class with great results, but here we didn't have 7 people to stand there all night, so we made islands out of spraypainted styroform with Playmobil figures glued on. We have
laid out in a room on top of cable rolls http://farm5.static.flickr.com/4001/4676418230_5d99d74c02_m.jpg
The connections between the islands are on cards stuck in the styrofoam with pencils. We had clip boards for the kids with pens attached, and printed off a few hundred of the islands without the connections. There were little bags of gummibears as the prize.
About 30 seconds after the official opening we had the first kids itching to play. The goal was to find the cheapest way to Treasure Island (which was not the shortest way). The kids were all excited about the islands, milling around, looking at them, reading the signs, filling out the map. Almost all of the kids solved the problem without help, just a few needed help. Some adults who tried were arithmetically challenged, not being able to add up the prices to get the complete price.
But everyone had a good time, we had a board up with the automaton generated by dot, the state transition table, and some information on Dijkstra's algorithm and what a finite state automaton is anyway. I tried to make the case for this bizarre mathematical stuff some guys did before there were computers that are suddenly really useful so that the government continues to fund basic research ;)
We needed about 170 Euros for the material and the prizes, and spent 2 days with two people making the islands. Now we just have to figure out where to store them, because we are going to do this again!