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.

Photos

• Teachers in Japan, preparing to be islands.
• Nametags for the Treasure Island game.
• Mr. Kazuhiro Sato, a Japanese elementary school teacher, proves John Donne incorrect by demonstrating that under suitable circumstances, at least one man can be an island.

Other Resources

• Wikipedia: Finite State Automata
• The Mathmaniacs web site has a similar activity (lesson 5), and a related one (lesson 6)

Curriculum Links

The Treasure Hunt game is an exercise in recording directions and creating a map. We like to run it in a big open space, with students running from island to island, but it can also be done at a more sedate pace in a classroom. The following activities extend the same ideas into the more abstract domains of language and probability.

New Zealand Curriculum Achievement Objectives

• Mathematics Level 2: Position and orientation
  • Describe different views and pathways from locations on a map.
• Mathematics Level 3: Probability
  • Investigate simple situations that involve elements of chance by comparing experimental results with expectations from models of all the outcomes, acknowledging that samples vary.
• Technology Level 2: Planning for practice
  • Develop a plan that identifies the key stages and the resources required to complete an outcome.
• Technology Level 2: Technological systems
  • Understand that there are relationships between the inputs, controlled transformations, and outputs occurring within simple technological systems.

ACM K12 Model Curriculum

• Level I (Grades 6-8) Topic 11: Understand the graph as a tool for representing problem states and solutions to complex problems.

Great Principles of Computer Science

• Computation