Embedded Files
We will use a passcode lock as an example that we can use to learn more about FSMs and how to program them. Suppose we have a door that can only be unlocked if the four digits of a specific number are entered in sequentially. You can only input the digits one at a time, left to right, and inputting the wrong digit forces you to start over. Once the door is unlocked, any further input will cause the door to lock. Opening the door again requires the user to re-enter the correct sequence, regardless of what input was used to close the door. With so many possible combinations, one would think that an FSM to describe such a lock would need a plethora of states. However, we will see it can be condensed down to just five states.
Suppose the passcode is 2534. Thus, the only possible way to unlock the door is by inputting 2, then 5, then 3, then 4 in that exact order. Inputting 2 and then another number that is not 5 will reset the lock, forcing you to start over from the beginning. Each time you guess a digit, it is either right or wrong, which means there are only two possible transitions from leaving a state. As for our output, the door is either unlocked (U) or locked (!U).
Let’s start with the initial state of the lock. By default, no guesses have been made. Thus the first digit has not been guessed yet. We can call this state SX, indicating that the first digit has not been correctly guessed yet. From this state, if we guess any digit that’s not 2, nothing changes, and the door remains locked. If we do correctly guess 2, however, we can move on to the next state: S2 (indicating that the first digit, 2, has been guessed).
From S2, inputting the wrong digit (anything that’s not 5) will reset the lock, causing the machine to go back to SX. Correctly guessing 5, however, advances us to state S25. From this state, the process repeats. Incorrectly guessing the next digit (anything that’s not 3) will return you to SX, whereas correctly guessing the next digit will change the state to S253. It should be no surprise here that wrongly guessing the next digit (anything that’s not 4) will once again revert the lock back to SX. Guessing the correct digit will move us to the final state, S2534. Since we have correctly guessed the passcode, the door will be unlocked upon transitioning to this state. From here, any new input will reset the lock, returning the machine back to state SX and locking the door.
The below figure shows the diagram of the passcode lock state machine in two forms. The top graph shows the block diagram that shows the FSM as a black box with a single input and a single output. The lower figure shows the FSM representation as a directed graph. States are shown with circles and transitions are shown as arcs. Each arc is labeled with the input condition that initiates it and the output it creates. A line similar to a fraction line in math is used to separate input symbols from output symbols. The inputs are shown above the line and the outputs below the line. For example, the arc that goes from SX to S2 has an input that is T (a correct guess) and an output that is !U (the lock is not opened.)
Report abuse