Finite-state machine

A finite state automaton (EA, also state machine, state machine, English finite state machine (FSM ) ) is a model of behavior composed of states, state transitions, and actions.

An automaton is called finite if the set of states that it can take (later called S) is finite. An IO is a special case from the set of machines. A state of storing the information about the past, ie, it reflects the changes of the input since the system start up at the current time. A state transition indicates a change of state of the EA and is described by the logical conditions that must be met in order to make the transition. An action, the output of the EA, which is carried in a particular situation. There are four types of actions

An IO can be represented as a state transition diagram as shown in Figure 1. In addition, several types of transition tables (or state transition tables) are used. The following table shows a very common form of transition tables: the combination of the current state of (B) and input (Y) leads to the next state (C ). The complete information about the possible actions is specified by means of footnotes. A definition of the EA, which includes the full information is output, it is possible with state tables, which are defined individually for each condition (see virtual EA).

The definition of the EA was originally introduced in the theory of automata and later adopted in computer technology.

State machines are mainly used in the development of digital circuits, modeling the application behavior ( controls), generally in software engineering as well as word and speech recognition.

  • 5.1 Hardware
  • 5.2 Software
  • 5.3 Reliable computer as EA Server

Classification

In general, two groups of EA are distinguished: acceptors and transducers.

Acceptors

You accept and acknowledge the input signal and by their condition the result to the outside. Usually symbols (letters) are used as input. The example in Figure 2 shows an EA, the "good" accepted the word. Acceptors are mainly used in the word and voice recognition.

Transducers (transducer)

Transducers generate output depending on state and input with the help of actions. They are mainly used for control tasks, in principle, two types are distinguished:

Moore and Mealy automata are equivalent. One can be converted into the other. In practice, most mixing models are used.

Another classification of the EA is made by the distinction between deterministic (DEA ) and non- deterministic (NEA ) machines. In the deterministic automaton exists for each state exactly one transition for each possible input. In non - deterministic automata, there can be no or more than one transition for the possible input.

An EA, which consists of only one state is called a combinatorial EA. He uses only input actions.

The logic of the EA

The next state and the output of the EA is a function of the input and the current state. Figure 5 shows the flow of logic.

The mathematical model

There are different definitions, depending on the type of EA. An acceptor is a 5-tuple ( Σ, S, S0, δ, F), wherein:

  • Σ is the input alphabet ( a finite non-empty set of symbols),
  • S is a finite non empty set of states,
  • S0 is the initial state, and an element of S,
  • δ is the state transition function: δ: S × Σ → S,
  • F is the set of final states, and a (possibly empty ) subset of S.

A transducer is a six - tuple ( Σ, Γ, S, S0, δ, ω ), wherein:

  • Σ is the input alphabet ( a finite non-empty set of symbols),
  • Γ is the output alphabet ( a finite non-empty set of symbols),
  • S is a finite non empty set of states,
  • S0 is the initial state, and an element of S,
  • δ is the state transition function: δ: S × Σ → S,
  • ω is the output function: ω: S × Σ → Γ,

If the output function is a function of state and input alphabet ( ω: S × Σ → Γ ), then there is a Mealy model. If the output function depends only on the state ( ω: S → Γ ), then it is a Moore model.

Optimization

An EA is optimized by the state machine is the least number of states have been found, which fulfills the same function. This problem can be solved for example by means of coloring algorithms.

Implementation

Hardware

In digital circuits EA are built with the help of programmable logic controllers, logic gates, flip- flops or relays. Hardware implementation usually requires a register to save the state variable, a logic unit which determines the state transitions and a second logic unit, which is responsible for the output.

Software

In software development generally the following concepts can be used to model and implement applications using state machines:

  • Event-driven finite state machine
  • Virtual finite state machine

Reliable computer as EA Server

All in the real world existing digital computers have a finite amount of memory and can thus only a finite (though very large ) number of accept digital switching states. They can therefore be regarded as a subset of the finite state machine. However, it is often more useful for theoretical considerations to consider it instead as a subset powerful automata models, such as the Turing machine.

Representation of finite state machines

The general rules for drawing a state transition diagram are as follows:

  • Circles represent states dar. In the circle the name of the state is.
  • Arrows represent the transitions between states dar. On each arrow is, what conditions enable the transition.
308139
de