Finite-state machine

Simple examples are: vending machines, which dispense products when the proper combination of coins is deposited; elevators, whose sequence of stops is determined by the floors requested by riders; traffic lights, which change sequence when cars are waiting; combination locks, which require the input of a sequence of numbers in the proper order.

[4][5] A turnstile, used to control access to subways and amusement park rides, is a gate with three rotating arms at waist height, one across the entryway.

Initially the arms are locked, blocking the entry, preventing patrons from passing through.

Depositing a coin or token in a slot on the turnstile unlocks the arms, allowing a single customer to push through.

The arrow into the Locked node from the black dot indicates it is the initial state.

A state is a description of the status of a system that is waiting to execute a transition.

A transition is a set of actions to be executed when a condition is fulfilled or when an event is received.

In some finite-state machine representations, it is also possible to associate actions with a state: Several state-transition table types are used.

The complete action's information is not directly described in the table and can only be added using footnotes.

[further explanation needed] An FSM definition including the full action's information is possible using state tables (see also virtual finite-state machine).

They support actions that depend on both the state of the system and the triggering event, as in Mealy machines, as well as entry and exit actions, which are associated with states rather than transitions, as in Moore machines.

[citation needed] The Specification and Description Language is a standard from ITU that includes graphical symbols to describe actions in the transition: SDL embeds basic data types called "Abstract Data Types", an action language, and an execution semantic in order to make the finite-state machine executable.

[citation needed] There are a large number of variants to represent an FSM such as the one in figure 3.

In addition to their use in modeling reactive systems presented here, finite-state machines are significant in many different areas, including electrical engineering, linguistics, computer science, philosophy, biology, mathematics, video game programming, and logic.

In computer science, finite-state machines are widely used in modeling of application behavior (control theory), design of hardware digital systems, software engineering, compilers, network protocols, and computational linguistics.

[6] Acceptors (also called detectors or recognizers) produce binary output, indicating whether or not the received input is accepted.

[7] For example, the set of binary strings with an even number of zeroes is a regular language (cf.

The problem of determining the language accepted by a given acceptor is an instance of the algebraic path problem—itself a generalization of the shortest path problem to graphs with edges weighted by the elements of an (arbitrary) semiring.

5: a deterministic finite automaton (DFA) that detects whether the binary input string contains an even number of 0s.

Classifiers are a generalization of acceptors that produce n-ary output where n is strictly greater than two.

In control applications, two types are distinguished: Sequencers (also called generators) are a subclass of acceptors and transducers that have a single-letter input alphabet.

This concept is useful in cases where a number of finite-state machines are required to work together, and when it is convenient to consider a purely combinatorial part as a form of FSM to suit the design tools.

, then it can be readily converted to an output-equivalent Mealy machine by setting the output function of every Mealy transition (i.e. labeling every edge) with the output symbol given of the destination Moore state.

The converse transformation is less straightforward because a Mealy machine state may have different output labels on its incoming transitions (edges).

[18] Optimizing an FSM means finding a machine with the minimum number of states that performs the same function.

More specifically, a hardware implementation requires a register to store state variables, a block of combinational logic that determines the state transition, and a second block of combinational logic that determines the output of an FSM.

The following concepts are commonly used to build software applications with finite-state machines: Finite automata are often used in the frontend of programming language compilers.

Such a frontend may comprise several finite-state machines that implement a lexical analyzer and a parser.

Starting from a sequence of characters, the lexical analyzer builds a sequence of language tokens (such as reserved words, literals, and identifiers) from which the parser builds a syntax tree.

The lexical analyzer and the parser handle the regular and context-free parts of the programming language's grammar.

Combinational logic Finite-state machine Pushdown automaton Turing machine Automata theory
State diagram for a turnstile
A turnstile
Fig. 1 UML state chart example (a toaster oven)
Fig. 2 SDL state machine example
Fig. 3 Example of a simple finite-state machine
Fig. 4: Acceptor FSM: parsing the string "nice".
Fig. 5: Representation of an acceptor; this example shows one that determines whether a binary number has an even number of 0s, where S 1 is an accepting state and S 2 is a non accepting state .
Fig. 6 Transducer FSM: Moore model example
Fig. 7 Transducer FSM: Mealy model example
Fig. 9 The circuit diagram for a 4-bit TTL counter, a type of state machine