Abstract machine

A vending machine or an abstract machine is in computer science, especially in automata theory, the model of a digital discrete-time computer. Whether it is possible or advisable, such a machine to actually build, it is initially irrelevant. The simplification of the skills makes it easier to understand the behavior of a machine and compare.

The machine concept plays a central role in theoretical computer science. In computability theory and in complexity theory about the machines provide the underlying calculation term. Machines also play in practical computer science a crucial role, for example in the compiler. In digital technology machines are used for control in digital and hybrid systems. Such control machines have applications among others in the computer architecture in computer networks and in reactive systems.

Behavior of an automaton

The general behavior of an automaton is always the same: the machine is presented as an input sequence of characters from the outside. The machine is located in a state. Each time an input character arrives, may depend on the input character and the current state of a new state, the successor state set ( state transition or transition). Can be the set of possible state transitions which define the behavior of the machine, as understand the program of the machine.

Deterministic and non- deterministic automata

If the next state by the current state and the input character is always given clearly, then one speaks of a deterministic automaton. But in general one can allow a margin (degrees of freedom ) for the state transitions. The machine must then select on the same pair of state and input character among several possible candidates a successor state arbitrarily. This is known as a non- deterministic automaton. The nondeterminism is then welcome if you want to model the behavior of the environment, which can not entirely accurate knows ( do not know ), or if you want to leave open possibilities for different implementations ( do not care).

Most allowed in addition to non-deterministic state transitions to even spontaneous state transitions, which are those that take place without input character ( ε - transitions).

Machines with and without output

Machines that handle only their state transitions are also called transition systems.

There are also machines that distinguish a certain subset of its states as final states. If an input word, leads the automaton of an excellent state, the start state to a final state, then we say the machine accepts the input word. Such a machine is called therefore an acceptor. An acceptor is to define a formal language, namely the set of all finite words that accepts the machine.

Finally, there are automata with output, or transducers. You assign either each state ( Moore machine ) or each pair of state and input character ( Mealy machines) to an output character. In this way a machine is a processing unit.

Classes of machines

After the allocation that has a machine is available, one can divide the machines into classes. Instead class of machines is also said automaton model. The acceptors of each class can be assigned to its accepted language. It turns out that every class of automata corresponds in this way a class of formal languages. Known classes of machines (each with abbreviations for the deterministic and the nondeterministic variant):

The amount of the machines are as follows with the quantities of classes of languages ​​and grammars in relationship (see Chomsky hierarchy ):

Whether LBA ⊃ DLBA really true, or whether the DLBAs the same class of languages ​​accepted as the LBA is not yet known.

Advanced machine concepts

Nondeterministic machines should not be confused with stochastic automata. The latter organize the state transitions to probabilities, while the former only talk about possibilities. For probability statements nondeterministic automata are not suitable.

There are also other types of machines that are not based on the sequential reading a command. Some of the more popular machines are:

  • Variants of Turing machine with two dimensional tape or multiple tapes
  • Cellular Automata
  • ω - automata for infinite input
  • Neural Networks
  • Petri nets

Applications

Of practical relevance for programming are mainly finite state machines and pushdown automata: they offer a simple structure that can be many complex problems can be solved clearly. In the compiler example, they are used to implement parsers implementations of network protocols often use a finite state machine to model their current state. The navigation options in a wizard can be very well expressed as a finite state machine and workflow management uses these concepts for the modeling of workflows. The file tree of an operating system is not really a tree but a finite state machine with the states and inodes as the file name as input character.

Even with the implementation of sequential hardware model of finite automata is used, there usually called Finite State Machine (FSM ).

  • Automata Theory
Compiler construction Uniqueness quantification Degrees of freedom (physics and chemistry) Nondeterministic algorithm State transition system Finite state transducer Finite-state machine Context-sensitive language Two-Stack Push Down Automaton Formal grammar Non-deterministic Turing machine Deterministic finite automaton Parsing Wizard (software) Filename
25436
de