Finite State Automata (Treasure Hunt)

Activity 11
Treasure Hunt—Finite-State Automata

Summary

Computer programs often need to work through a sequence of symbols — this could be letters or words in a document, or even the text of another computer program. Computer scientists often use something called a finite-state automaton (FSA) to do this job. An FSA follows a set of instructions to check whether the computer can recognize a word or a string of symbols. In this activity, you'll work with something that acts just like an FSA — a treasure map!

Curriculum Links

• Mathematics: Developing logic and reasoning — using words and symbols to describe and continue patterns
• Social Studies
• English

Skills

• Simple map reading
• Recognizing patterns
• Logic
• Following instructions

Ages: 9 and up

Materials

You will need:

• One set of island cards (keep the instructions hidden from anyone trying to draw the map!)

Copy the Photocopy Master: Island cards and cut them out. Fold each card along the dotted line and glue it so the island's name shows on the front, with the instructions hidden on the back.

Each child will need:

• Worksheet: Find your way to the riches on Treasure Island
• A pen or pencil

There are also optional extension activities. For these, each child will need:

• Worksheet: Treasure islands
• Worksheet: The mysterious coin game

---

Treasure Island

Introduction

Your goal is to find Treasure Island. Friendly pirate ships sail along fixed routes between islands in this part of the world, offering rides to travelers. Every island has two ships leaving from it, called Ship A and Ship B, and you get to choose which one to take. Your job is to find the best route to Treasure Island.

At each island, you may ask to board either Ship A or Ship B (not both). Someone at the island will tell you where that ship takes you next — but the pirates themselves don't have a full map of all the islands! You'll need to use your own map to keep track of where you've been and which ships you've taken.

Demonstration

(Note: This example uses a different map from the main activity.)

On a board or projector, draw a diagram of three islands, like the one shown here. Then have three children each hold one of the demonstration cards (the routes on these cards are different from the ones used in the main activity).

Start at Pirates' Island and ask for Ship A. The child holding that card should direct you to Shipwreck Bay — mark this route on your map. At Shipwreck Bay, ask for Ship A again, and you'll be sent back to Pirates' Island. Mark that route too. This time, ask for Ship B instead. This route leads to Dead Man's Island — and there you're stuck, since no ships leave from there!

---

The Activity

Choose 7 children to act as "islands." Each one holds a card showing their island's name, with secret instructions hidden on the back. Spread them out randomly around the room or playground.

The rest of the children each get a blank map. Their task is to find a route from Pirates' Island to Treasure Island, carefully marking each step on their map as they go. (It works best to send children off one at a time, so they can't overhear each other's routes.)

For fast finishers: Try to find more than one possible route.

Follow-up discussion

What is the fastest route to Treasure Island? What would a very slow route look like? Some routes might loop back on themselves — can you find an example? (For instance, the sequences BBBABAB and BBBABBABAB both eventually reach Treasure Island.)

---

Finite-State Automata

There's another way to draw this kind of map. Instead of names, the islands are shown as numbered circles, and the final island — the one with the treasure — is drawn as a double circle. The question becomes: which routes will get you to that final island?

For example:

• In one map, you only reach the double circle if your sequence contains an odd number of As (for example, AB, BABAA, or AAABABA).
• In another map, you only get there with a sequence that alternates between A and B (like AB, ABAB, ABABAB, and so on).
• In a third map, you just need your sequence to include at least one B (the only sequences that fail are A, AA, AAA, AAAA, and so on).

---

Worksheet Activity: Treasure Islands

Can you hide your buried treasure so well that it's hard to find? Now it's your turn to design a map!

1. Here's a more detailed version of the same map idea used earlier — it represents the same routes as before. Computer scientists use this kind of quick diagram to design patterns and sequences. Try drawing your own version, showing clearly how your pirate ships travel between islands. Then design your own blank maps and island cards. What's the shortest, most efficient sequence of routes to reach your Treasure Island?

1. Test your map on your friends! Give them a sequence of As and Bs and see whether they can figure out which island they end up on. You can invent all kinds of games and puzzles using this idea of finite-state automata.

1. Here's another way to use the same idea: build sentences by choosing a random path through a map and writing down the words you pass along the way. Try creating your own version — you might even end up with a funny story!

---

Worksheet Activity: The Mysterious Coin Game

Some friends downloaded a game where a robot flips a coin, and players have to guess whether it will land heads or tails. At first, the game seemed simple — they figured they'd have a fair, 50/50 chance of guessing correctly. But after playing for a while, they began to suspect something odd. It seemed like there was a hidden pattern in the coin flips. Was the game rigged? Surely not!

They decided to investigate. Joe wrote down the results of many coin tosses (using "h" for heads and "t" for tails). Can you spot a predictable pattern in the results?

There's actually a very simple "map" that describes the pattern of coin tosses. See if you can figure it out. (Hint: it only needs 4 "islands.")

---

What's it all about?

Finite-state automata help computers process a sequence of characters or events, one step at a time.

A simple, everyday example is calling a phone number and hearing a message like: "Press 1 for this... Press 2 for that... Press 3 to talk to a person." Each button you press is an input for a finite-state automaton on the other end of the line. Sometimes these systems are simple, and sometimes they're very complex. If you ever feel like you're being sent in circles by an automated phone system, that's usually a mistake in how the automaton was designed — and it can be very frustrating!

Another example is withdrawing cash from a bank machine. The machine's program guides you step-by-step through a sequence of choices, and inside the program, all of the possible paths are stored as a finite-state automaton. Every button you press moves the automaton to a new "state." Some states carry instructions for the machine, such as "dispense $100 in cash," "print a receipt," or "eject the card."

Some computer programs even use maps like this to work with English sentences — both creating new sentences and understanding sentences typed in by a user. In the 1960s, a computer scientist created a famous program called "Eliza" (named after a character called Eliza Doolittle). Eliza pretended to be a therapist, asking questions like "Tell me about your family" or "Do go on." The program didn't actually understand anything it was saying — but it seemed convincing enough, and some users were trusting enough, that a few people really believed they were talking to a real person.

While computers aren't very good at truly understanding human language, they are excellent at processing artificial (made-up, structured) languages. One important example is a programming language — the special language used to write computer software. Computers use finite-state automata to read programs written in these languages and translate them into basic instructions that the computer can carry out directly.

---

Solutions and hints

The Mysterious Coin Game

The mysterious coin game follows a hidden map. If you trace it out, you'll notice that the first two coin tosses in every group of three always come out the same.