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)
Translations and other versions:
- Arabic Language Version
- Chinese Language Version
- Italian Language Version
- French Language Version
- Greek Language Version
- Portugese (Brazil) Language Version
- Polish Language Version
- Slovenian Language Translation
Videos
Photos
Related Resources
- 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:
-
- 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:
- [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.
-
- If you want to find out more:
- 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.
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 2: Position and orientation
-
- Mathematics Level 3: Probability
- Investigate simple situations that involve elements of chance by comparing experimental results with expectations from models
- Mathematics Level 3: Probability
-
- 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: Planning for Practice
- Technology Level 2: Technological Systems
- Understand that there are relationships between the inputs, controlled transformations, and outputs occurring within simple technological systems.