Substitute Lesson Plan: Finite-State Automata (Treasure Hunt)

Objective

Students will learn what a finite-state automaton (FSA) is and how computer scientists use these "maps" to process sequences of symbols (like letters, words, or key presses). By acting out a treasure hunt using island cards, students will practice following instructions, simple map reading, recognizing patterns, and logical reasoning.

Materials

• Set of Island Cards (Photocopy Master, pages 92–95) — cut out, folded, and glued so the island name is on the front and instructions are hidden on the back (prepare ahead if possible; if not pre-made, see note below)
• Worksheet Activity: "Find your way to the riches on Treasure Island" (page 91) — one per student
• Pen or pencil for each student
• Board or OHP for the demonstration map
• Note for substitute: If the island cards are not already prepared, do the Demonstration only (using the board), skip the full class Activity, and spend more time on the Wrap-up discussion and If Time Remains section instead.

Warm-up (~5 min)

1. Ask students: "Have you ever used a phone menu that says 'Press 1 for this, Press 2 for that'?" Let a few students share experiences.
2. Explain: "Today we're going to be pirates and computer scientists at the same time! We'll use a treasure map to understand something called a finite-state automaton — a set of instructions a computer follows to process a sequence, like your key presses on a phone menu."
3. Tell students the goal: navigate from Pirates' Island to Treasure Island by choosing Ship A or Ship B at each island you land on.

Main Activity (~25 min)

1. Demonstration (5 min): Draw the three-island demonstration map on the board (Pirates' Island, Shipwreck Bay, Dead Man's Island). Have three students each hold one demonstration card (with routes hidden on the back).
2. Start at Pirates' Island, ask for Ship A. The student holding that card tells you where it leads (Shipwreck Bay). Mark the route on the board map.
3. At Shipwreck Bay, ask for Ship A again — you return to Pirates' Island. Mark it.
4. This time ask for Ship B — you're taken to Dead Man's Island, where "No ships sail" — you're stuck! Mark this too.
5. Point out: the final board map should now show all three routes drawn in.

1. Main Activity (20 min): Choose 7 students to be "islands." Give each one an island card (name showing, instructions hidden on back). Position them around the room.
2. Give every other student a blank worksheet map (page 91) and a pencil.
3. Send students one at a time to Pirates' Island to begin their journey. At each island, they ask the student holding that card for "Ship A" or "Ship B," and the island-holder tells them (from the hidden instructions) where that ship goes next.
4. Students carefully mark their route on their worksheet map as they go, continuing until they reach Treasure Island (or get stuck).
5. Remind students to send classmates off one at a time so no one overhears another student's route in advance.
6. Fast finishers: Challenge them to go back and find a second, different route to Treasure Island.

Wrap-up / Exit Ticket (~10 min)

1. Bring the class back together and ask:
2. "What was the quickest route you found to Treasure Island?"
3. "Did anyone find a very slow route, or one with a loop (where you go around in a circle before eventually reaching the treasure)?"
4. Explain that some routes may involve loops — for example, two different sequences like BBBABAB and BBBABBABAB can both eventually reach Treasure Island.
5. Exit Ticket: On a scrap of paper, have each student write:
6. The sequence of Ships (As and Bs) they used to reach Treasure Island (or where they got stuck).
7. One sentence answering: "Where else might a real computer use a set of step-by-step instructions like this?" (Remind them of the phone menu example from the warm-up, or mention that bank cash machines and computer programs work this way too.)
8. Collect the exit tickets as students leave.

If Time Remains

Read aloud the "What's it all about?" explanation (page 99) about real-world finite-state automata: phone menus, bank cash machines, and the 1960s computer program "Eliza," which pretended to be a psychotherapist by following a script of leading questions. Ask students: "Why do you think some people were fooled into thinking Eliza was a real person?" Discuss briefly as a class.