Finite State Automata

Learning Resource Type

Classroom Resource

Subject Area

Digital Literacy and Computer Science

Grade(s)

5, 6, 7, 8

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.

 

Digital Literacy and Computer Science (2018) Grade(s): 5

DLCS18.5.2

Create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm.

UP:DLCS18.5.2

Vocabulary

  • algorithm
  • debug
  • detect
  • logical errors

Knowledge

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 (2018) Grade(s): 5

DLCS18.5.3

Create an algorithm that is defined by simple pseudocode.

UP:DLCS18.5.3

Vocabulary

  • algorithm
  • pseudocode

Knowledge

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 (2018) Grade(s): 5

DLCS18.5.4

Create a simple pseudocode.

UP:DLCS18.5.4

Vocabulary

  • pseudocode

Knowledge

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 (2018) Grade(s): 5

DLCS18.5.5

Develop and recommend solutions to a given problem and explain the process to an audience.

UP:DLCS18.5.5

Vocabulary

  • process

Knowledge

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 (2018) Grade(s): 6

DLCS18.6.5

Identify algorithms that make use of sequencing, selection or iteration.

UP:DLCS18.6.5

Vocabulary

algorithm sequence selection iteration

Knowledge

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 (2018) Grade(s): 6

DLCS18.6.6

Identify steps in developing solutions to complex problems using computational thinking.

UP:DLCS18.6.6

Vocabulary

  • computational thinking

Knowledge

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 (2018) Grade(s): 6

DLCS18.6.7

Describe how automation works to increase efficiency.

UP:DLCS18.6.7

Vocabulary

  • automation

Knowledge

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 (2018) Grade(s): 7

DLCS18.7.3

Create algorithms that demonstrate sequencing, selection or iteration.

UP:DLCS18.7.3

Vocabulary

  • algorithm
  • sequence
  • selection
  • iteration

Knowledge

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 (2018) Grade(s): 7

DLCS18.7.6

Create and organize algorithms in order to automate a process efficiently.

UP:DLCS18.7.6

Vocabulary

  • algorithm

Knowledge

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 (2018) Grade(s): 8

DLCS18.8.5

Discuss the efficiency of an algorithm or technology used to solve complex problems.

UP:DLCS18.8.5

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 (2018) Grade(s): 8

DLCS18.8.6

Describe how algorithmic processes and automation increase efficiency.

UP:DLCS18.8.6

Vocabulary

  • algorithmic process
  • automation

Knowledge

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.

CR Resource Type

Learning Activity

Resource Provider

CS Unplugged

License Type

Attribution Share Alike

Resource Provider other

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

Custom License Type (URL)

https://creativecommons.org/licenses

Accessibility

Text Resources: Content is organized under headings and subheadings
Video resources: includes closed captioning or subtitles

Comments or Notes

CS Unplugged is a free resource.

Approved Date

ALSDE LOGO

This site may contain links to other websites or content belonging to or originating from third parties or links to websites and features in banners or other advertising. Such external links are not investigated, monitored, or checked for accuracy, adequacy, validity, reliability, availability, or completeness by us. WE DO NOT WARRANT, ENDORSE, GUARANTEE, OR ASSUME RESPONSIBILITY FOR THE ACCURACY OR RELIABILITY OF ANY INFORMATION OFFERED BY THIRD-PARTY WEBSITES LINKED THROUGH THIS SITE.
Alabama Learning Exchange © 2002-2023 by Alabama State Department of Education is licensed under Attribution-NonCommercial-ShareAlike 4.0 International

Design by Adaptive Theme