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

Wikipedia: Finite State Automata
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:
- Kara, programming with state machines
- TuringKara, turing machines illustrated
jayisgames has a game made in Flash that teaches the concept of Finite State Automata called Manufactoria.

Expand

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

Expand

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.