Automat (computer science)

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

The term automaton plays a central role in theoretical computer science . In computability theory and complexity theory, for example, automata are the underlying computation concept. Automata also play a decisive role in practical computer science , for example in compiler construction . In the digital technology machines are used for control in the digital and hybrid systems used. Such automatic control systems have applications in computer architecture , in computer networks and in reactive systems .

Behavior of a machine

The basic behavior of a machine is always the same: An input as a sequence of characters is presented to the machine from the outside . The machine is in a certain state. Every time an input character arrives, depending on the input character and the current status, a new status, the subsequent status , can occur ( status transition or transition ). The set of possible state transitions that defines the behavior of the automaton can be understood as the program of the automaton.

Deterministic and nondeterministic automata

If the subsequent state is always clearly given by the current state and the input character , then one speaks of a deterministic automaton. In general, however, one can also allow a margin ( degrees of freedom ) for the state transitions. The machine can then arbitrarily choose a subsequent state from several possible candidates for the same pair of state and input characters. Then one speaks of a nondeterministic automaton. Nondeterminism is welcome if you want to model the behavior of the environment that you don't know exactly ( don't know ), or if you want to leave options open for different implementations ( don't care ).

Usually, in addition to non-deterministic state transitions, spontaneous state transitions are also permitted, i.e. those that take place without input characters (ε transitions).

Machines with and without dispensing

Automata that only process their state transitions are also called transition systems .

There are also automata that mark a certain subset of their states as final states . If an input word leads the machine from an excellent state, the start state , to one of the end states, then the machine is said to accept the input word. Such a machine is therefore called an acceptor . An acceptor is suitable for defining a formal language , namely the set of all finite words that the automaton accepts.

Finally, there are also dispensing machines, so-called transducers . You assign either to each state ( Moore automata ) or to each pair of state and input characters ( Mealy automata ) an output character. In this way, a machine forms a processing unit.

Classes of automatons

The machines can be divided into classes according to the means available to an automaton. Instead of class of machines, one also says machine model . The acceptors of the respective class can be assigned their accepted language. It turns out that every class of automata corresponds in this way to a class of formal languages. Well-known classes of automata are (each with abbreviations for the deterministic and the nondeterministic variant):

Turing machines (DTM / NTM): In addition to its internal state, a Turing machine also has access to an infinite tape on which a movable read / write head can write characters and read them later. Both classes accept the type 0 languages ( recursively enumerable language ). The Turing machine also defines the term predictability . See Church's thesis .
Linear restricted machines (DLBA / LBA): The only difference between the linearly limited automata and the Turing machines is that the accessible part of the band is limited by the size of the input. Nondeterministic LBA exactly accept the type 1 languages ( context sensitive languages ); the question of whether this also applies to deterministic LBA is still an open problem.
Push- button machines (DPDA / PDA): In addition to one of a finite number of internal states, a basement machine also has access to the basement, a stack on which characters can be temporarily stored for later processing. The PDAs accept type 2 languages ( context-free languages ). The DPDAs accept the deterministic context-free languages .
Finite machines (DFA / NFA): A finite automaton only knows finitely many states. Both classes accept the type 3 languages ( regular languages ).

The set of automata is related to the sets of language classes and grammars as follows (see also Chomsky hierarchy ):

Chomsky hierarchy	Language class		nondeterministic automaton		deterministic automaton
Type 0 grammar	${\ displaystyle {\ mathcal {\ color {blue} RE}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} NTM}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} DTM}}}$
Type 1 grammar	${\ displaystyle {\ mathcal {\ color {blue} CS}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} LBA}}}$	${\ displaystyle \ supseteq}$	${\ displaystyle {\ mathcal {DLBA}}}$
Type 2 grammar	${\ displaystyle {\ mathcal {\ color {blue} CF}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} PDA}}}$	${\ displaystyle \ varsupsetneq}$	${\ displaystyle {\ mathcal {DPDA}}}$
Type 3 grammar	${\ displaystyle {\ mathcal {\ color {blue} REG}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} NFA}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} DFA}}}$

It is not yet known whether LBA ⊃ DLBA really applies or whether the DLBAs accept the same language class as the LBAs.

Further classes of machines are:

Two-cellar machine: In contrast to the cellar machine, the two-cellar machine has two cellars available. A Turing band can be simulated through the cellar pair. The two-cellar machines are therefore equivalent to the Turing machines. Syntactic restrictions of this model lead to the characterization of type 1 and type 2 languages.
Register machines: In addition to its internal state, a register machine has a sequence of registers, which are storage cells for natural numbers on which elementary arithmetic operations can be carried out. Register machines are just as powerful as Turing machines.

Extended machine terms

Nondeterministic automata must not be confused with stochastic automata . The latter assign probabilities to the state transitions, while the former only talk about possibilities. Nondeterministic automata are therefore not suitable for making probability statements.

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

Variants of the Turing machine with a two-dimensional belt or with several belts
Cellular automata
ω-automata for infinite inputs
Neural Networks
Petri nets
Algebraic calculation models

Applications

Finite automata and push-down automata are of practical relevance for programming : they offer a simple structure with which many complex problems can be solved clearly. In the compiler, they are, for example, the implementation of parsers used, the reactions of networking protocols often use a finite state machine to around their current state model . The navigation options in a wizard can also be expressed very well as a finite automaton, and workflow management uses these concepts to model work processes.

The finite state machine model is also used in the implementation of sequential hardware , there usually referred to as a finite state machine (FSM).