Activity 11

Treasure Hunt—Finite-State Automata

Summary

Computer programs often need to look at a sequence of symbols, like the letters or words in a document. Sometimes they even look at the text of another computer program. To do this, computer scientists often use something called a finite-state automaton (say it: aw-TOM-uh-ton). An FSA follows a set of instructions to check if the computer can recognize a word or string of symbols. In this activity, we'll use something just like an FSA — treasure maps!

Curriculum Links

• Mathematics: Using logic and reasoning — using words and symbols to find 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 the kids 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 extra challenge 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 sail along set routes between islands. Each island has two ships you can catch, called Ship A and Ship B. You can only choose one at a time. At each island you land on, ask for either Ship A or Ship B — not both. The person at the island will tell you where that ship takes you next. But be careful: the pirates don't have a 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 demo uses a different map from the real activity.)

Draw a diagram of three islands on the board, like the example shown. Copy the three demo cards and give one to each of three children to hold. Remember, 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 send you to Shipwreck Bay. Mark this route on your map. At Shipwreck Bay, ask for Ship A again — this sends you back to Pirates' Island. Mark that too. This time, ask for Ship B instead. This route leads to Dead Man's Island... where you'll get stuck, because no ships leave from there!

Cards for the demonstration activity

The cards show:

• Ship A →
• Ship B →

And one special card reads: "No ships sail from Dead Man's Island!"

---

The Main Activity

Pick 7 children to be "islands." Give each one a card showing their island's name, with secret instructions on the back. Spread them out randomly around the room or playground.

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

Fast finishers: Try to find more than one route!

Follow-up Discussion

What's the fastest route? What would be a really slow one? Some routes loop back on themselves — can you find an example? (For instance, both BBBABAB and BBBABBABAB will get you to Treasure Island.)

---

Finite-State Automata

There's another way to draw this kind of map: using numbered circles for islands, with arrows showing the routes. The final island — the one with the treasure — gets a double circle.

What sequences of moves get you to the final island?

• Map (a): You reach the double circle (island 2) only if your path has an odd number of A's (like AB, BABAA, or AAABABA).
• Map (b): You only reach the double circle by alternating A and B (like AB, ABAB, ABABAB...).
• Map (c): Your path just needs at least one B in it. (The only paths that DON'T work are A, AA, AAA, AAAA, and so on.)

---

Worksheet Activity: Treasure Islands

Can you hide your treasure well? How tricky can you make it to find?

1. Here's a more detailed way to draw the same kind of map. It shows the same routes as before. Computer scientists use this quick method to design patterns.

Draw your own simple plan like this, showing the routes your pirate ships travel. Then make your own blank maps and island cards. What's the shortest path to your Treasure Island?

2. Can your friends follow your map? Give them a sequence of A's and B's and see if they land on the right island.

You can invent all kinds of games and puzzles using this idea of finite-state automata!

3. 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 making your own — maybe even a funny story!

---

Worksheet Activity: The Mysterious Coin Game

Some friends downloaded a game where a robot flips a coin, and they had to guess heads or tails. At first, it seemed easy — they figured they'd have a 50/50 chance of winning. But after a while, they got suspicious. It seemed like there was a pattern in the coin flips. Was the game rigged? Surely not!

They decided to investigate. Joe wrote down the results of many flips (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 find a pattern? There's a simple "map" with just 4 islands that describes the pattern of coin flips. Can you figure it out?

---

What's It All About?

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

Here's a simple example: when you call a phone number and hear "Press 1 for this... Press 2 for that... Press 3 to talk to a person," your key presses are inputs for a finite-state automaton on the other end. This kind of conversation can be simple or very complicated. Sometimes you get stuck going in circles, because there's a strange loop built into the system. That's actually a design mistake — and it can be really frustrating for the caller!

Another example is a bank's cash machine. The computer inside leads you through a series of steps. All the possible paths are stored as a finite-state automaton. Each button you press moves the automaton to a new "state." Some states carry instructions like "give out $100 in cash," "print a receipt," or "eject the card."

Some computer programs use maps just like the ones in this activity 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 had conversations with people, pretending to be a therapist, asking things like "Tell me about your family" or "Do go on." The program didn't actually understand anything people said — but it seemed believable enough that some people really thought they were chatting with a human therapist!

While computers aren't great at truly understanding human language, they're very good at handling artificial languages — languages made up with strict rules. One important kind of artificial language is a programming language. Computers use finite-state automata to read programs and turn them into simple instructions the computer can carry out directly.

---

Solutions and Hints

The Mysterious Coin Game

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