Finite State Machine

Finite State Machine (FSM) is one of the most used models in the development of software for computers and digital circuits with sequential logic. This model describes a process in terms of a number of well-defined states, the possible ways of moving from one state to another, and the actions that take place at the transition between states. FSMs are particularly useful in modeling systems which may be in one of many possible states at any given time and which can change from one state to another upon the receipt of some input or event.

The principal elements of FSM

• ‍States: These are the various states or modes in which the system may be found. At any one time, the FSM is in one particular state or the other.
• ‍Transition: It is the definition of the procedures or rules that outline how a certain system is to transition from one state to another.These transitions are stimulated by events or signals which are recognized by the system.
• ‍Input Symbols: These are signals that lead to the change of system status. All the state changes are activated by specific input symbols.
• ‍Actions: These are the activities or the outcomes that are bound to happen when there is a shift or when there is a transition into a new situation.

FSMs are especially used in a situation whereby the operation of an object or a system is a function of its past or present state. It offers a clear approach to describe the desired behavior of a system in view of the input/output relations, and for this reason, they are vitally important in software development, hardware design, robotics, and AI.

Perhaps the simplest example of an FSM is a turnstile. The turnstile has two modes of operation: namely the Locked and Unlocked modes. It starts in Locked state, when a coin is inserted it goes into the Unlocked state which allows a person to move through. In this case once the person exits the detail it is set back to Locked. The input to the system will be the act of putting in a coin into the slot and going through the turnstile and the output will be the act of the turnstile opening and closing.

FSMs are of two categories

• ‍Deterministic Finite State Machine (DFSM): In a DFSM there is only one transition from a given state for a given input. This does not pose a problem in design and analysis since every specific input will always result to a certain and known state.
• ‍Non Deterministic Finite State Machine (NDFSM): In an NDFSM in a specific state for specific input, there can be more than one possible transition. This approach is more flexible than the previous one; however, it has its own problems to deal with in management and realization.

FSMs can be used in designing sequential logic circuits – circuits whose output depends not only on the current input, but also on inputs that were applied in the past. One of the interesting applications is their use in determination of control units of CPUs in which several states describe different stages of the instruction processing such as fetching, decoding, executing and storing the results.

In the domain of software development, FSMs are used to define the manner in which a program is to control its own flow. It is used in constructing parsers, defining protocols, and dealing with the user interface, among other things. For instance, when dealing with user interfaces an FSM can manage several screens or states and the shift from one state to another based on user interaction such as a button or key press.

Finite State Machines are used in robotics and game design to help in controlling one or more behaviors or modes of entities such as robots or game characters. For example a game character could have states such as Idle, Walking, Jumping and Attacking and the change from one state to the other could be triggered by player actions or some event happening in the environment.

FSMs are quite suitable for modelling complex systems and, when combined with other computational techniques or when the input/output format is modified, can provide robust models. However, there is a disadvantage of FSMs and that is when there are many states the FSMs could be rather unhandy. This is why at times more elaborate models for instance the Hierarchical State Machines or Statecharts are used to address complexity.

The Finite State Machine FSM can be defined as a powerful and reliable computational model, which finds its application in analyzing systems that at any time can be in one among a set of possible states. In this way, through the establishment of actions FSMs give a systematic way of describing the dynamic behaviour of systems in various fields of computing and engineering including logic circuits, software and much more.