Finite State Automata

Classroom Resource Information

Title:

Finite State Automata

URL:

https://classic.csunplugged.org/finite-state-automata/

Content Source:

Other
CS Unplugged
Type: Learning Activity

Overview:

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. Computer scientists often use a finite-state automaton to do this. A finite-state automaton (FSA) follows a set of instructions to see if the computer will recognize the word or string of symbols. We will be working with something equivalent to a FSA—treasure maps!

The goal of the students is to find Treasure Island. Friendly pirate ships sail along a fixed set of routes between the islands in this part of the world, offering rides to travelers. Each island has two departing ships, A and B, which you can choose to travel on. You need to find the best route to Treasure Island. At each island you arrive at you may ask for either ship A or B (not both). The person at the island will tell you where your ship will take you to next, but the pirates don’t have a map of all the islands available. Use your map to keep track of where you are going and which ship you have traveled on.

Content Standard(s):
 Digital Literacy and Computer Science DLIT (2018) Grade: 5 2) Create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm. Examples: Program the movement of a character, robot, or person through a maze. Define a variable that can be changed or updated. Digital Literacy and Computer Science DLIT (2018) Grade: 5 3) Create an algorithm that is defined by simple pseudocode. Digital Literacy and Computer Science DLIT (2018) Grade: 5 4) Create a simple pseudocode. Digital Literacy and Computer Science DLIT (2018) Grade: 5 5) Develop and recommend solutions to a given problem and explain the process to an audience. Digital Literacy and Computer Science DLIT (2018) Grade: 6 5) Identify algorithms that make use of sequencing, selection or iteration. Examples: Sequencing is doing steps in order (put on socks, put on shoes, tie laces); selection uses a Boolean condition to determine which of two parts of an algorithm are used (hair is dirty? True, wash hair; false, do not); iteration is the repetition of part of an algorithm until a condition is met (if you're happy and you know it clap your hands, when you're no longer happy you stop clapping). Digital Literacy and Computer Science DLIT (2018) Grade: 6 6) Identify steps in developing solutions to complex problems using computational thinking. Digital Literacy and Computer Science DLIT (2018) Grade: 6 7) Describe how automation works to increase efficiency. Example: Compare the amount of time/work to hand wash a car vs. using an automated car wash. Digital Literacy and Computer Science DLIT (2018) Grade: 7 3) Create algorithms that demonstrate sequencing, selection or iteration. Examples: Debit card transactions are approved until the account balance is insufficient to fund the transaction = iteration, do until. Digital Literacy and Computer Science DLIT (2018) Grade: 7 6) Create and organize algorithms in order to automate a process efficiently. Example: Set of recipes (algorithms) for preparing a complete meal. Digital Literacy and Computer Science DLIT (2018) Grade: 8 5) Discuss the efficiency of an algorithm or technology used to solve complex problems. Digital Literacy and Computer Science DLIT (2018) Grade: 8 6) Describe how algorithmic processes and automation increase efficiency.
Tags: algorithm, finite state automation, selection, sequence
For full descriptions of license types and a guide to usage, visit :
Video resources: includes closed captioning or subtitles

CS Unplugged is a free resource.

This resource provided by:
 Author: Aimee Bates