A5 - Finite State Machines

Suppose we creating a game where the up arrow makes the player jump, but only if the player is not already in the air. We may also want the down arrow to make the player duck, but only if the player in not already in the middle of a jump. You could imagine plenty of additional scenarios we could add to this, for example, an attack that is only possible while currently in the air. The logic here can get complicated pretty quickly. This type of problem, where we have several different scenarios or states, can be visualized easily by a diagram that we call a Finite State Machine, that looks like this:

Each oval in the diagram represents a state, each arrow represents a transition between states, and the label above each arrow represents an event that causes that transition to occur. Not shown in the diagram are things that happen during state transitions, such as a change in the player animation.

Once we have a finite state machine diagram, implementing the corresponding code is fairly simple. The above example may look something like this:

state = "standing":

while True: # infinite loop

    if state == "standing":
        if up_key_is_pressed:
            state = "jumping"
            player.current_animation = "jumping"
            continue

        if down_key_is_pressed:
            state = "ducking"
            player.current_animation = "ducking"
            continue

    if state == "jumping":
        if player.is_touching_ground():
            state = "standing"
            continue

    if state == "ducking":
        if up_key_is_pressed:
            state = "jumping"
            player.current_animation = "jumping"
            continue

        if not down_key_is_pressed:
            state = "standing"
            player.current_animation = "standing"
            continue

Note - continue will immediately start the next iteration of the loop without completing the current iteration.

For another example, see this page.

Task 1

Create the finite state diagrams on paper for the following two scenarios:

1. You are provided with a list of colours, and you need to determine if three primary colours appear consecutively anywhere in the list. Your diagram should have the following states, corresponding to the current number of colours seen:

   • zero
   • one
   • two

   Your diagram should have the following events over the transition arrows:

   • primary [for when a primary colour is encountered]
   • non-primary [for when any other colour is encountered]

   Your diagram should have arrows pointing to the following outcomes:

   • accept [three consecutive primary colours found]
   • reject [the string does not contains three consecutive primary colours]

2. You must determine if a string contains a valid email address. For the purpose of this exercise, we'll assume a valid email address is of the following form:

   • Starts with any number of alphanumeric chracters (which you can abbreviate as alnum) or periods
   • Is followed by a single @ symbol.
   • Is followed by any number of alphanumeric characters
   • Is followed by a period
   • Is followed by any number of alphanumeric characters and/or periods

   Your diagram should have the follwing states:

   • Before @ [the part of the email prior to @]
   • After @ [the part of the email after the @, but before any other dots]
   • After dot [the part of the email after the @, and after a dot comes at some point after the @]

   Your diagram should have the following events over the transition arrows:

   • alnum
   • .
   • @

   Your diagram should have arrows pointing to the following outcomes:

   • accept - the full string has been read and the email address is valid
   • reject - the string has been found to NOT be a valid email address

Task #2

In a file called a5.py, implement the email verification exercise you drew the diagram for above.