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