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

### Activity description (PDF)

- Instructions for Finite State Automata activity (English)
- Italian Language Version
- French Language Version
- Greek Language Version
- Portugese (Brazil) Language Version
- Polish Language Version
- Slovenian Language Translation
- Extra – An indoor version of this activity as an interactive powerpoint. Courtesy of Tom Cortina (CMU)

### Videos

### Photos

### Related Resources

- 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.
- 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:
- jayisgames has a game made in Flash that teaches the concept of Finite State Automata called Manufactoria.

### Curriculum Links

##### Great Principles of Computer Science [info]

- Computation

##### ACM K12 Curriculum [info]

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

##### New Zealand Curriculum [info]

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