Finite State Machines

• Computer Science
• Lower Secondary (Key Stage 3)

Y12 - Unit 2 - Problem Solving

Topic 6: Finite State Machines

Key Vocabulary:

Finite

State

Transition

In this lesson, you will

• Understand what is meant by a finite state machine
  
• List some of the uses of a finite state machine
  
• Draw and interpret simple state transition diagrams for finite state machines with no output
  
• Draw a state transition table for a finite state machine with no output

What is a finite state machine?

• It is not a “machine” in the sense of some physical, mechanical thing with moving parts
• It is an abstract representation of how something changes from one state to another in response to a condition or event
  

In a finite state machine (FSM):

• The machine can only be in one state at a time
  
• It can change from one state to another in response to an event or condition; this is called a transition
  
• The FSM is defined by a list of its states and the conditions for each transition
  
• There can be outputs linked to the FSM’s state, but we will be considering only FSMs with no output

Example: a turnstile

• A turnstile is used to control access to a railway platform
• It can be in one of two states: locked or unlocked
• Inserting a ticket unlocks the turnstile, allowing a single customer to pass through
• The arms are locked again until another ticket is inserted

FSM representing a turnstile

• Pushing the arm when the turnstile is in the locked state has no effect
  
• Putting another ticket in when in the unlocked state also has no effect

What is your ‘app for that’?

You have five minutes to work in pairs.

  

Think of an idea for an app that could have a positive impact on the world.

Think about how the user will interact with the app.

Write your ideas on a the next slide.

What is your
‘app for that’?

The Tappy Tap App

Over the next two and half lessons we will develop a new app called the Tappy Tap App. 

It will:

• Get users to click a moving blue dot as many times as they can within a time limit
• Give the user a point for each accurate click on the blue dot
• Move the blue dot each time it is clicked

Decompose the problem

Decomposition is breaking a problem down into more manageable chunks.

Programming an app for a mobile device can be a daunting task to undertake.

Decomposing the problem helps us make the task less daunting and more achievable.

Decompose the problem

Imagine that your job is to make the first level of a new platform game.

You might start by decomposing the problem in the following way:

• Create the layout of the level
• Add a user-controlled character
• Add enemies
• Add score, timer, and power-ups

Continue decomposing

When you arrive at each decomposed step, you can now decompose it further.

How might you decompose the ‘player movement’ step further?

• Add left and right movement
• Add a gravity effect
• Add the ability to jump

Success criteria

Welcome screen:

• Must show logo and instructions on how to play
  
• Must have a button that activates the game play once clicked
  

Game play:

• The game must last 15 seconds before automatically moving to the final score screen
  
• There must be a blue dot and a red dot that the user can press
  
• When the blue dot is pressed, the score must increase by one
  
• When the blue dot is pressed, the dot should move to a different place on the screen
  
• The red dot must also move to a different place on the screen when pressed, but the score will decrease by one
  

Final score:

• Must display the user’s score at the end of the game
  
• Must have a button to allow the user to return to the welcome screen
  

Decompose the 'Tappy Tap App'

Look at the requirements of the Tappy Tap App on your worksheet.

How would you decompose the problem?

Think/write/pair/share.

How did you decompose the problem?

App Lab demonstration

Log into App Lab using the login details given to you:

> go to code.org

> Create account 

> I'm a student 

> Sign up with Microsoft

> Enter the class code (will be given to you)

• Browse to ‘Start a new project’
• Select App Lab
• Rename your project ‘Tappy Tap App’
• Add a button to the screen

Design the home screen

Your task is to implement the design of the welcome screen (don’t forget to rename ‘screen1’ as ‘welcome screen’). Use your success criteria to help, as well as the sketched design on the right.

Explorer tasks:

• Add a new game screen
• Watch the following video (ncce.io/AppLabA4)
• Code the button to open the game screen

Play your future Tappy Tap App

Visit the following URL to play the game:

ncce.io/TappyTapAppL1

After a couple of goes, look at your success criteria and ask yourself whether or not the game meets all the criteria.