Why finite state machine

At first, this sounds silly to even make this distinction. What good is a set of decisions if the same input can result in moving to more than one state? The output of a state machine is its final state. It goes through all its processing, and then the final state is read, and then an action is taken. It processes, and when it gets to the end, the state is read and something external triggers the desired action for example, dispensing a soda can.

This is an important concept when it comes to non-deterministic finite state machines. Non-deterministic finite state machines are finite state machines where a given input from a particular state can lead to more than one different state.

A very simple way to represent this is with a state machine that looks like the one below, where a final state of t means that the string was accepted and matches the pattern.

Do you see the problem? There are a few ways to solve this problem. One is by backtracking. You simply take all the possible paths, and ignore or back out of the ones where you get stuck. This is basically how most chess playing computers work.

They look at all the possibilities — and all the possibilities of those possibilities — and choose the path that gives them the greatest number of advantages over their opponent. One of the interesting attributes of a non-deterministic machine is that there exists an algorithm to turn any non-deterministic machine into a deterministic one. However, it is often much more complicated. Fortunately for us, the example above is only slightly more complicated. In fact, this one is simple enough that we can transform it into a deterministic machine in our head, without the aid of a formal algorithm.

The machine below is a deterministic version of the non-deterministic machine above. In the machine below, a final state of t or v is reached by any string that is accepted by the machine. The non-deterministic model has four states and six transitions.

The deterministic model has six states, ten transitions and two possible final states. A moderately sized non-deterministic machine can produce an absolutely huge deterministic machine. Regular expressions and finite state machines are functionally equivalent. Anything you can accept or match with a regular expression, can be accepted or matched with a state machine.

Regular expressions and finite state machines also have the same limitations. In particular, they both can only match or accept patterns that can be handled with finite memory. At first, this looks like an easy job for a finite state machine. In other words, neither a regular expression nor a finite state machine can be constructed that will recognize all the strings that do match the pattern. Within any pair of tags, you may have any number of other matching pairs of tags.

There is a theoretical device that is similar to a state machine, called a Turing Machine. It is similar to a finite state machine in that it has a paper strip which it reads. But, a Turing Machine can erase and write on the paper tape. Explaining a Turing Machine will take more space that we have here, but there are a few important points relevant to our discussion of finite state machines and regular expressions.

Turing Machines are computationally complete — meaning anything that can be computed, can be computed on a Turing Machine. Since a Turing Machine can write as well as read from the paper tape, it is not limited to a finite number of states.

The paper tape can be assumed to be infinite in length. Turing Machines give us an imaginary mechanical device that lets us visualize and understand how the computational process works. It is particularly useful in understanding the limits of computation. Regardless of their limitations, state machines are a very central concept to computing. In particular, it is significant that for any non-deterministic state machine you can design, there exists a deterministic state machine that does the same thing.

This is a key point, because it means you can design your algorithm in whichever way is the easiest to think about. Once you have a working algorithm, you can convert it into whatever form is most efficient. A state machine is a behavior model. It consists of a finite number of states and is therefore also called finite-state machine FSM. Based on the current state and a given input the machine performs state transitions and produces outputs.

This introduction gives a short overview of the common basis and the differences between state machine types. The basic building blocks of a state machine are states and transitions. A state is a situation of a system depending on previous inputs and causes a reaction on following inputs.

One state is marked as the initial state; this is where the execution of the machine starts. A state transition defines for which input a state is changed from one to another. Consider the simple state machine above. It consists of two states, Off and On. On is the initial state here; it is activated when the state machine is executed.

The arrows between the states denote the possible state transitions. They define for which input a state change occurs. Here, the active state is changed from On to Off for the input buttonpressed , and back again to On for the same input. Please note: In automata theory an automaton reacts on inputs and produces outputs. There, the terms input and output are usually used for symbols which belong to an alphabet.

Modern state machines use an extended definition of inputs and outputs. Inputs can be events like a button click or a time trigger while outputs are actions like an operation call or a variable assignment. In the following, we will extend the simple switch example to explain the differences between Mealy and Moore machines as well as Harel statecharts and UML state machines. In automata theory, there are two basic types of finite-state machines FSM.

One of those is called Moore machine , named after its inventor Edward Moore, who introduced the concept in Moore machines consist of states and transitions. States are able to produce outputs , and the output is determined solely by the current state, not by any input. We extend the switch example above into a light switch with different brightness levels. Pressing the ON button switches the light on and toggles through the different brightness levels.

This behavior is modeled by the state machine below. The output of the state machine is simply the brightness level. As in Moore machines only states produce outputs, we need one dedicated state per brightness level:. Mealy machines were invented by George H. Mealy in In comparison with Moore machines, Mealy machines produce outputs only on transitions and not in states.

This often results in state diagrams with fewer states because more logic can be put on transitions. Be aware that both state diagrams, the Moore machine above and the Mealy one, describe exactly the same system. Indeed, automata theory states that you can always translate a Moore machine into a Mealy machine and vice versa, without losing any expressiveness.

Although Mealy machines can already reduce the number of required states, for complex systems such automatons get easily unmanageable. Harel concluded that " a state approach must be modular, hierarchical and well-structured" and introduced additional concepts like state composition and orthogonality.

Using composite states and sub diagrams, we are able to bring more depth into state diagrams, while keeping the diagrams clear and well-structured.

Regions help us to express orthogonality : Different substate machines that can be executed side by side. Events allow us to achieve broadcast communication and give us a strong means to describe complex behavior. Using guards, we can state that a certain event triggers a transition only if a given condition is met.