Finite State Automata

Treasure Hunt #

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)

Translations and other versions #

• Arabic language version
• Chinese language version
• Italian language version
• French language version
• Greek language version
• Portuguese (Brazil) language version
• Polish language version
• Slovenian Language Translation

Videos #

See our video page.

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 #

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

If you want to find out more #

• Wikipedia: Finite State Automata

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 #

• Computation

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