Finite State Automata

PDFs

Can't find a translation? Check our projects page for status.

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

Curriculum Links

Great Principles of Computer Science

ACM K12 Curriculum

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

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

Videos

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 circum

Extension

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.

Dateien

Other 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.
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
Merchant Taylors' School UK in it's free course on Moodle aimed at AS Computing has an activity in Finite State Machines based on Kara . Read also their Getting Started with Kara guide.
jayisgames has a game made in Flash that teaches the concept of Finite State Automata called Manufactoria.

Computer Science Unplugged