Activity 11

Treasure Hunt—Finite-State Automata

Summary

Computer programs often need to process a sequence of symbols — such as letters or words in a document, or even the text of another computer program. To do this, computer scientists often rely on a finite-state automaton (FSA): a set of instructions that checks whether a word or string of symbols is one the computer can recognize. In this activity, we'll work with something that behaves just like an FSA — treasure maps!

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 front shows the island's name and the back shows the instructions.

Each child will need:

• Worksheet: Find Your Way to the Riches on Treasure Island
• A pen or pencil

For the optional extension activities, each child will also need:

• Worksheet: Treasure Islands
• Worksheet: The Mysterious Coin Game

---

Treasure Island

Introduction

Your goal is to find Treasure Island. Friendly pirate ships travel along fixed routes between the islands in this part of the world, offering rides to travelers. Every island has two ships leaving from it, Ship A and Ship B, and you must choose one. At each island you reach, you may request either Ship A or Ship B — not both. The person at that island will tell you where your ship takes you next, but no single pirate has a map of the whole region. You'll need to use your own map to track where you've been and which ship you took each time.

Demonstration

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

Using an overhead projector or a board, draw a diagram of three islands as shown. Then copy the three demonstration cards, and have one student hold each card. (The routes on these cards differ from those used in the main activity.)

Start at Pirates' Island and ask for Ship A. The student holding that card should direct you to Shipwreck Bay — mark this route on your map. At Shipwreck Bay, ask for Ship A again; 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!

Activity

Choose 7 students to act as "islands." Each holds a card showing their island's name, with secret instructions on the back. Spread them out randomly around the room or playground. The remaining students each get a blank map and must trace a route from Pirates' Island to Treasure Island, carefully marking their path. (It works best to send students one at a time, so they can't overhear each other's routes.)

Fast finishers: Try to find more than one route to Treasure Island.

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: islands become numbered circles, and the final island — the one holding the treasure — is drawn as a double circle. The question becomes: which routes (sequences of A's and B's) lead to that final, double-circled island?

For example:

• One map only reaches the treasure island if the sequence contains an odd number of A's (like AB, BABAA, or AAABABA).
• Another map only reaches it with a sequence that strictly alternates between A and B (AB, ABAB, ABABAB, and so on).
• A third map reaches the treasure as long as the sequence contains at least one B — the only sequences that fail are strings of all A's (A, AA, AAA, AAAA...).

---

Worksheet Activity: Treasure Islands

Can you hide your buried treasure well? How difficult can you make it for someone to find it? Now it's your turn to design a map!

1. Here's a more advanced way of drawing the same kind of map — the circles-and-arrows style computer scientists use to design these route patterns. Draw your own version so you can clearly see the paths your pirate ships travel. Then create your own blank maps and island cards. What's the shortest sequence of routes to reach your Treasure Island?

1. How well can your friends follow your map? Give them a sequence of A's and B's and see if they land on the correct island. You can invent all sorts of games and puzzles using this idea of finite-state automata.

1. Here's a way to build sentences by choosing random paths through a map and writing down the words you land on as you go. Try building your own version — maybe even turn it into a funny story!

---

Worksheet Activity: The Mysterious Coin Game

Some friends downloaded a game from the internet in which a robot flips a coin, and players guess whether it will land heads or tails. At first, the game seemed simple — they figured they'd have a 50/50 chance of winning. But after a while, they grew suspicious: there seemed to be a pattern in the coin tosses. Was the game rigged? Surely not!

They decided to investigate. Joe wrote down the results of several rounds (h = heads, t = tails):

```
h h t h h t h h h t t h h h h t t h t t t h h h h h t h h h
t t t h h h t t t h h h h h h t t h t t t t t h t t h t t t
h h h t t h h h t h h h h h h h h h t t h h h t t t t h h h
h h t t t t t t t
```

Can you spot a predictable pattern? There's a very simple "map" that describes this sequence of coin tosses — see if you can work it out. (Hint: it has just 4 "islands.")

---

What's It All About?

Finite-state automata are used in computer science to help a computer process a sequence of characters or events.

A simple real-world example: when you dial a phone number and hear "Press 1 for this... Press 2 for that... Press 3 to speak with an operator," your key presses are inputs feeding a finite-state automaton on the other end of the line. That dialogue can be simple or quite complex. Sometimes you get looped back to an earlier point because of a flaw — a peculiar loop — in the automaton's design. When that happens, it's a design error, and it can be maddening for the caller!

Another example is withdrawing cash from a bank machine. The machine's program guides you through a sequence of steps, and internally, every possible sequence is represented as a finite-state automaton. Each 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 actually process English sentences using maps like the one shown earlier in this activity. These programs can generate sentences on their own and also process sentences typed in by a user. In the 1960s, a computer scientist created a famous program called "Eliza" (named after Eliza Doolittle) that could hold conversations with people. The program pretended to be a psychotherapist, asking leading questions like "Tell me about your family" and "Do go on." Although Eliza didn't actually understand anything, it was convincing enough — and its human users trusting enough — that some genuinely believed they were talking to a real therapist.

While computers aren't especially good at understanding natural human language, they're very effective at processing artificial languages — languages built with strict, well-defined rules. One important example is the programming language. Computers use finite-state automata to read in programs and translate them into basic instructions that the computer can carry out — or "execute" — directly.

---

Solutions and Hints

The Mysterious Coin Game

The mysterious coin game follows a map in which, if you trace it through, you'll notice that the first two coin tosses in every group of three produce the same result.