Activity 11

Treasure Hunt — Finite-State Automata

What Is This About?

Computer programs often need to look at a list of symbols, like letters or words. Computer scientists use something called a finite-state automaton (say: FI-nite-state aw-TOM-uh-ton), or FSA for short, to do this job. An FSA is a set of steps a computer follows to check something, like a word.

In this activity, we will use treasure maps to learn how an FSA works!

What You Need to Know

This activity connects to:

• Math: finding and following patterns
• Social Studies
• English
• Skills: reading simple maps, spotting patterns, using logic, following directions

This activity works best for kids age 9 and up.

What You Need

• A set of "island cards" (keep the instructions hidden from the players!)
• A worksheet called "Find your way to the riches on Treasure Island"
• A pen or pencil

There are also bonus activities using two more worksheets: "Treasure islands" and "The mysterious coin game."

---

Treasure Island

The Story

Your goal is to find Treasure Island. Friendly pirate ships sail between islands. At each island, there are two ships you can take: Ship A or Ship B. You pick only one.

The person at each island will tell you where that ship goes next. But no single pirate knows the whole map! You must use your own map to keep track of where you've been and which ships you picked.

Show How It Works

(This example map is different from the real activity.)

Draw three islands on a board, like this:

Pirates' Island → Shipwreck Bay → Dead Man's Island

Copy three cards and give one to each of three kids to hold.

Start at Pirates' Island. Ask for Ship A. The child holding that card sends you to Shipwreck Bay. Draw this route on your map.

At Shipwreck Bay, ask for Ship A again. You go back to Pirates' Island! Draw this on your map too.

Now ask for Ship B instead. This route leads to Dead Man's Island. No ships leave from there — so you're stuck!

---

The Main Activity

Pick 7 kids to be "islands." Give each one a card showing their island's name on the front, with secret directions on the back.

Spread the kids around the room or playground.

Give the rest of the class a blank map. Each player must find a path from Pirates' Island to Treasure Island, marking the route on their map as they go.

Tip: Send players one at a time, so they can't hear the answers from other players ahead of them.

For fast finishers: Try to find more than one path to Treasure Island!

Let's Talk About It

• What is the fastest path to Treasure Island?
• What would a very slow path look like?
• Some paths loop around and repeat. Can you find one? (For example, the paths BBBABAB and BBBABBABAB both lead to Treasure Island.)

---

Another Way to Draw a Map

We can also draw maps using circles and arrows. Each island is shown as a numbered circle. The island with the treasure gets a double circle.

• In Map (a), you only reach the treasure if your path has an odd number of A's. (Examples: AB, BABAA, AAABABA)
• In Map (b), you only reach the treasure if A and B take turns the whole way. (Examples: AB, ABAB, ABABAB)
• In Map (c), you reach the treasure as long as your path has at least one B in it.

---

Bonus Worksheet: Treasure Islands

Can you hide your treasure really well? How tricky can you make your map?

1. Look at this map style — it's a fast, simple way to draw routes, just like real computer scientists do! Try drawing your own map. Then make blank maps and island cards for your friends. What is the shortest path to your treasure?

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

1. You can also build sentences by picking a random path through a word map and writing down each word you pass. Try making your own silly story this way!

---

Bonus Worksheet: The Mysterious Coin Game

Some friends found a game online. A robot flips a coin, and players guess heads or tails. At first, it seemed easy — they thought they had a 50/50 chance to win.

But after a while, they got suspicious. The coin flips seemed to follow a pattern! Was the game unfair?

They wrote down the results (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 the hidden pattern?

There is a simple map that can explain this pattern. It only needs 4 islands. Can you figure it out?

---

What's This All About?

Finite-state automata help computers handle a list of symbols or events, one at a time.

Here's one example: when you call a company and hear "Press 1 for this... press 2 for that..." — each button you press is like a move in a finite-state automaton on the other end. Sometimes the system loops you around in circles by mistake. That's annoying, and it means there's an error in how the system was built!

Another example is a bank cash machine. It leads you through steps one at a time. Every button you press moves you to a new "state." Some states tell the machine to do something, like "give out $100" or "print a receipt" or "return the card."

Some computer programs even use maps like this to work with English sentences! They can make up sentences or understand ones typed in by a person. In the 1960s, a scientist made a famous program called "Eliza." It pretended to be a therapist, asking questions like "Tell me about your family." It didn't really understand anything — but some people still thought they were talking to a real person!

Computers aren't great at understanding everyday language. But they're very good at reading artificial languages — languages made just for computers. One example is a programming language. Computers use finite-state automata to read programs and turn them into simple instructions they can follow.

---

Answer Key

The Mysterious Coin Game

Here is the map that makes the coin-toss pattern:

If you follow this map, you'll notice something neat: the first two coin flips in every group of three are always the same!