Finite State Machines (FSM)

Finite State Machines is a model of computation that can be used to model the behavior of a system.

Example


Here is an example of a simple state machine:


This state machine models a button state machine that controls the power to some other system.  A state is represented as a circle, in this example: "Power On" and "Power Off".  A transition is represented by an arrow leading from one state to another: "Button click".

Let us do a quick run through of what this represents.  We imagine that this state machine is controlling the lights in your room.  You enter the room, and it is dark.  This means that you are currently in the state "Power Off".  You want to turn on the lights, and in order to that you click the button that turns the light on.  This is taking the transition from "Power Off" --> "Power On" through the "event" Button Click.

How does this Apply to Computer Science?


I first learned the concept of state machines in my computer architecture course, where it we tracked the behavior of a system.  It would then continue to come up in my upper division course, including: Operating Systems, Embedded Systems, Compilers and many more classes.  It was clear that state machines have their uses throughout computer science.

Using Enums in Java to simulate a State Machine


There are many ways you can create a state machine in Java, such as maintaining a string called "state" that enters a switch statement or if/else ladder.  Also alternatively you could use a integer to keep track of your state by assigning a number to each state.

The best way to create a state machine in Java is to use enums to represent each of your states.  Using enums allows you to store certain values into your enums, which will be useful in some situations.

public static enum state {
           state1, state2, state3, state4, state5, state6;
}

To "transition" between states, you can use if/else statements or switch statements.  I choose to show a switch statement in this example:

switch(currentState) {
case state1: currentState = state2; break;
case state2: currentState = state3; break;
case state3: currentState = state4; break;
case state4: currentState = state5; break;
case state5: currentState = state6; break;
default: //Invalid state
}

This switch statement models a FSM that enters the next state every cycle of the system.  How do I make this applicable to a real, simple program.

You can create state machine that is controlled by user input, by using Scanner with System.in.

Scanner sc = new Scanner(System.in)

The next thing you want to do is to create a loop that accepts a user input, or other parameter, and checks it against it's current state to see if a transition needs to be made.

while(true) {
         //loop
}

or you can designate a leave state that exits the loop

while(currentState != state6) {
        //loop
}

For a more complete version of the code above: State Machine Example

Concluding Thoughts


Many of you will probably have written some code in one form or another that is similar to this computational model.  Based on a current "State" and given new information, change the "State" of your program to this.  This is a more formal way of describing this action.  I have found that knowing the basics of this is important to programming for embedded systems.  Basically any model that requires a user input will need to be based on a state machine, because of the you need a "state" to describe how an object at a certain point of time during operation.  The state machine I have described in this example is a Moore state machine, because it relies solely on the entry action, or the event that caused the transition.  There is another model of the state machine that relies on both the current state as well as the event action.  You can find more details about the difference between the two at the Wiki page: Finite State Machine

Comments

Post a Comment

Popular posts from this blog

Uncle Bob's Clean Architecture

Image
The basis of my current understanding of architecture comes from the brilliant mind of Robert C. Martin (Uncle Bob). You can find the original post through his blog , which I strongly encourage you to read. In this post I'll try to summarize some of the key points I've understood from his post. Clean Architecture Source Clean architecture is a design used to emphasize the structure and relation of your various code components to promote the idea of Dependency Rule , such that "source code dependencies only point inwards" . Clean architecture is able to promote this by defining that your software system consists of various layers , that can be organized in such a way that the layers point in one direction, and a dependency graph will not have circular reference. The reason this is important is because it allows you to keep closely code related, and increase clarity of how components fit into your system. Explaining the Layers We can really separate out this ...
Read more

C4 Model: Describing Software Architecture

Image
The point behind a presentation of Visualizing Software Architecture , by Simon Brown, was that we need to standardize the way software developers communicate with each other in respect to our discussions of software architecture. As part of Simon's consultation, one exercise he gave to software architects was a simple task to white board the architecture of a software system. The results he received varied immensely, and there was never a defacto standard format that he received from this exercise. When inspecting the feedback from the participants, the general answer was that it was easy to come up with the design, but difficult to properly put their ideas onto paper, or white board in this case. White Board Example, c4model.com Simon sought to start a movement by defining a set of organizational rules to help us describe our software architecture with a set of standard terminologies. His work has let to C4 Model , which stands for C ontext, C ontainers, C omponents,...
Read more

Running RabbitMQ with Docker

Image
Short post today, mostly just wanted to how to setup RabbitMQ for local development. Refer back to my previous post to learn more about RabbitMQ. Prerequisite Docker For complete guide reference, check out the Docker Hub Website for RabbitMQ . Why use Docker? Before starting my current job at iHerb, I would go straight for the Windows installation (my development environment) for all of my development tools needs. It was straight forward and "just worked" a lot of the time. What I've begun to realize experimenting with all these different tooling and services is that things can get a bit cluttered, you will have a bunch of supporting systems that need to be run - caches, queues, databases and it can be a hassle to manage them through window services and executables. Additionally some of these require additional dependencies outside of the executable itself, which prompts you to install even more tooling. The great thing about docker is that it defi...
Read more