# ALEX Classroom Resource

## 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. Unpacked Content Evidence Of Student Attainment:Students will: create an algorithm to solve a problem. detect and debug logical errors within an algorithm.Teacher Vocabulary:algorithm debug detect logical errorsKnowledge:Students know: an algorithm is a logical set of steps to solve a problem. detecting and debugging logical errors within an algorithm will ensure the algorithm serves to solve a problem successfully.Skills:Students are able to: create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm.Understanding:Students understand that: debugging an algorithm is searching for logical errors within the algorithm. an algorithm is a set of steps to solve a problem. how to create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm. Digital Literacy and Computer Science DLIT (2018) Grade: 5 3) Create an algorithm that is defined by simple pseudocode. Unpacked Content Evidence Of Student Attainment:Students will: create set of steps that is written in simple pseudocode.Teacher Vocabulary:algorithm pseudocodeKnowledge:Students know: simple pseudocode resembles language used to communicate with computers.Skills:Students are able to: create an algorithm that is written in simple pseudocode.Understanding:Students understand that: an algorithm that is written in simple pseudocode is similar to an algorithm written using a programming language. Digital Literacy and Computer Science DLIT (2018) Grade: 5 4) Create a simple pseudocode. Unpacked Content Evidence Of Student Attainment:Students will: create simple pseudocode.Teacher Vocabulary:pseudocodeKnowledge:Students know: how to write an algorithm in pseudocode.Skills:Students are able to: create simple pseudocode.Understanding:Students understand that: pseudocode is simple phrases of instruction that mimics the logic of a programming language. 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. Unpacked Content Evidence Of Student Attainment:Students will: develop and recommend solutions to a given problem. explain the development process to an audience.Teacher Vocabulary:processKnowledge:Students know: steps of the problem-solving process. many solutions exist to solve a problem.Skills:Students are able to: develop and recommend solutions to a given problem. share their process with others. Understanding:Students understand that: problems can have multiple solutions. 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). Unpacked Content Evidence Of Student Attainment:Students will: find algorithms that demonstrate the three basic programming structures.Teacher Vocabulary:algorithm sequence selection iterationKnowledge:Students know: differences between the three basic programming structures.Skills:Students are able to: explain the differences in sequencing, selection, and iteration.Understanding:Students understand that: differences exist in sequencing, selection, and iteration. Digital Literacy and Computer Science DLIT (2018) Grade: 6 6) Identify steps in developing solutions to complex problems using computational thinking. Unpacked Content Evidence Of Student Attainment:Students will: use the problem solving or design thinking process to think logically through a previously solved complex problem.Teacher Vocabulary:computational thinkingKnowledge:Students know: how to define the problem. how to plan solutions. how to implement a plan. how to reflect on the results and process. how to iterate through the process again.Skills:Students are able to: identify the steps involved with formulating problems and solutions in a way that can be represented or carried with or without a computer.Understanding:Students understand that: computational thinking is formulating problems and solutions in a way that can be represented or carried out with or without a computer. 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. Unpacked Content Evidence Of Student Attainment:Students will: explain how an automated activity or system increases productivity.Teacher Vocabulary:automationKnowledge:Students know: how automation works to increase efficiency.Skills:Students are able to: describe how automation increases efficiency.Understanding:Students understand that: automation works to increase efficiency. 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. Unpacked Content Evidence Of Student Attainment:Students will: create an algorithm using one of the three basic programming structures: sequencing, selections, or iterations.Teacher Vocabulary:algorithm sequence selection iterationKnowledge:Students know: how to use the programming structures to create algorithms and how many algorithms make use of all three programming structures.Skills:Students are able to: create and recognize various programming structures found in algorithms.Understanding:Students understand that: each structure sequencing, selections, and iterations have a purpose. 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. Unpacked Content Evidence Of Student Attainment:Students will: use algorithms to automate a process such as sorting numbers in a random list or playing cards in a deck.Teacher Vocabulary:algorithmKnowledge:Students know: algorithms can be used to automate a process efficiently.Skills:Students are able to: use search and sort algorithms to automate organizing a set.Understanding:Students understand that: algorithms organized and applied to the appropriate task can significant increase proficiency. Digital Literacy and Computer Science DLIT (2018) Grade: 8 5) Discuss the efficiency of an algorithm or technology used to solve complex problems. Unpacked Content Evidence Of Student Attainment:Students will: examine a given artifact used to aid in problem solving. discuss the efficiency of that artifact in problem solving.Knowledge:Students know: that many solutions exist to solve a problem.Skills:Students are able to: communicate their opinion on the efficiency of problem solving methods.Understanding:Students understand that: while many solutions exist for a problem, some are better suited to meet specific needs, such as efficiency. Digital Literacy and Computer Science DLIT (2018) Grade: 8 6) Describe how algorithmic processes and automation increase efficiency. Unpacked Content Evidence Of Student Attainment:Students will: explain how algorithms and automation have and can increase efficiency.Teacher Vocabulary:algorithmic process automationKnowledge:Students know: how algorithmic processes and automation have increased efficiency.Skills:Students are able to: explain how algorithmic processes and automation increase efficiency.Understanding:Students understand that: automation is a useful tool for increasing efficiency. while many things can and have been automated, not everything can be automated using algorithmic processes.
Tags: algorithm, finite state automation, selection, sequence
License Type: Attribution Non-Commercial Share Alike
For full descriptions of license types and a guide to usage, visit :
https://creativecommons.org/licenses
AccessibilityText Resources: Content is organized under headings and subheadings
Video resources: includes closed captioning or subtitles
Comments

CS Unplugged is a free resource.

This resource provided by:
 Author: Aimee Bates