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

Automaton

Start State

Accept State

End State

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

     FSM representing a turnstile

• Suppose the turnstile will not accept any ticket – it has to be a valid one for the journey
  
• Can you draw a new state transition diagram with two extra inputs: valid ticket and invalid ticket?
  
• There will be a third state – ticket inserted

     FSM representing a turnstile

     Applications of FSMs

• Robotics
  
• Video games industry
  
• Design of digital hardware systems
  
• Design of compilers and network protocols
  
• Definition of languages, and to decide whether a particular word is allowed in a language

     Finite state automaton

• A FSM which has no output is known as a finite state automaton
  
• It has a start state and a set of end or accept states
  
• If the automaton can reach a final state, it is said to accept the input
  
• Starting in an initial state, the automaton processes a sequence of symbols and follows it to the target state
  
• The symbols depend on the application – they usually represent events

     Notation

     Recognising a language

• A finite state system accepts a string

     if there is a path from the start state to the end or accept state labelled by         the symbols C1, …., Cn

• The language recognised by the FSM consists of all strings accepted by it.

     Applications of FSMs

• Which of the following strings will be accepted by this finite state automaton?

 aaac  badc  adadbd  ac  bdaac  bd

     Worksheet 6

• Now try the questions in Task 1 of Worksheet 6

     Worksheet 6

• Now try the questions in Task 1 of Worksheet 6

     Worksheet 6

• Now try the questions in Task 1 of Worksheet 6

     Worksheet 6

• Now try the questions in Task 1 of Worksheet 6

https://www.madebyevan.com/fsm/ 

     State transition tables

• An alternative representation of a FSM is a State Transition Table
  
• The FSM below accepts two inputs a and b
  
• The transition table shows what the next state is for any input. What strings does it accept?

     Example

• Complete the transition table for the FSM shown
  
• Which of the following strings are accepted?

     Worksheet 6

• Now try the questions in Task 2 of Worksheet 6

     Worksheet 6

• Now try the questions in Task 2 of Worksheet 6

     Worksheet 6

• Now try the questions in Task 2 of Worksheet 6

https://www.madebyevan.com/fsm/ 

     Worksheet 6

• Now try the questions in Task 2 of Worksheet 6

     Worksheet 6

• Now try the questions in Task 2 of Worksheet 6

     How NES Games Use State Machines For Everything

     Y12 - Unit 2 - Problem Solving

     Topic 6: Finite State Machines