Finite State Automata

PDFs
Can't find a translation? Check our projects page for status.
Treasure Hunt

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

  • Rowboat
Videos 
Photos 
  • Teachers in Japan, preparing to be islands

    Teachers in Japan, preparing to be islands

  • Nametags for the Treasure Island game

    Nametags for the Treasure Island game

  • Mr. Kazuhiro Sato, a Japanese elementary school teacher, proves John Donne incor

    Mr. Kazuhiro Sato, a Japanese elementary school teacher, proves John Donne incorrect by demonstrating that under suitable circum

Extension 
Other Resources 
 
Anonymous wrote 3 years 1 week ago

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.

 
weberwu wrote 4 years 6 weeks ago

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!

Log In