Finite State Automata

Contents

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

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
A student mapping out their journey between islands

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.

More activities and lessons:
- An indoor version of this activity as an interactive powerpoint. Courtesy of Tom Cortina (CMU)
- 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.
- The Mathmaniacs web site has a similar activity (lesson 5), and a related one (lesson 6)
- [Requires Java installed] SwissEduc has a programming environment called Kara, 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:
  - Kara, programming with state machines
  - TuringKara, turing machines illustrated
- [Registration and software download required]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.

Additional resources:
- 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.

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

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