Nondeterministic finite automaton

Graphic representation of an NEA

A non-deterministic finite state machine ( NEA ; English nondeterministic finite automaton , NFA ) is a finite state machine , in which there are several equivalent ways to state transition. In contrast to the deterministic finite automaton , the possibilities are not unique, so the automaton is not given which transition to choose.

definition

Formally, an NEA can be defined as a quintuple (5-tuple) . The following applies here: ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle \ left (Q, \ Sigma, \ Delta, S, F \ right)}$

{\ displaystyle Q}

is a finite, non-empty set of states ( ).

{\ displaystyle \ left | Q \ right | <\ infty}

{\ displaystyle \ Sigma}

is a finite, non-empty input alphabet .

{\ displaystyle \ left | \ Sigma \ right | <\ infty}

{\ displaystyle \ Delta \ subseteq (Q \ times \ Sigma) \ times Q}

is the transition relation (or transition relation).

{\ displaystyle S \ in Q}

is the start state.

${\ displaystyle F \ subseteq Q}$ is a (finite) set of possible accepting states (final states). If the automaton fails in one state after reading the input word , it is part of the language . ${\ displaystyle w \ in \ Sigma ^ {*}}$ ${\ displaystyle F}$ ${\ displaystyle w}$ ${\ displaystyle L \ left ({\ mathcal {A}} \ right)}$

behavior

If the NEA reads the input symbol in one state , then it changes non-deterministically to a successor state that is given by the transition relation. The automaton has the choice between all states for which applies. ${\ displaystyle q}$ ${\ displaystyle a}$ ${\ displaystyle p}$ ${\ displaystyle (q, a, p) \ in \ Delta}$

If there is no such status, the machine stops prematurely and rejects the entry.

An input word is considered accepted if there is a change of state for a given sequence in which the machine does not stop prematurely and the last state is an accepting state. ${\ displaystyle w}$ ${\ displaystyle w}$ ${\ displaystyle \ Delta}$

Transition as a function

Alternatively, the transitions can also be defined by a transition function , which is then mapped into a number of states:

{\ displaystyle {\ mathcal {A}} = \ left (Q, \ Sigma, \ delta, S, F \ right)}

With

{\ displaystyle \ delta \ colon (Q \ times \ Sigma) \ to {\ mathcal {P}} (Q)}

Since the function can also map to the empty set, so that it can apply, a premature stop is also possible here. ${\ displaystyle \ delta (q, a) = \ varnothing}$

Epsilon transitions

An NEA that recognizes language for language

{\ displaystyle \ alpha}

{\ displaystyle \ alpha ^ {*}}

NEAs can also be defined in such a way that state transitions are possible in which no input character is read. Before or after reading a character, an NEA can randomly change its state. The states that can be changed are connected by transitions that read the empty word (sometimes also ) instead of a symbol . These state changes are called transitions or steps . In graphical representations of NEAs, the transitions are shown as edges labeled with (or ) and are therefore also called edges. ${\ displaystyle \ varepsilon}$ ${\ displaystyle \ lambda}$ ${\ displaystyle \ varepsilon}$ ${\ displaystyle \ varepsilon}$ ${\ displaystyle \ varepsilon}$ ${\ displaystyle \ lambda}$ ${\ displaystyle \ varepsilon}$

Formally, these transitions are made possible by extending the transition relation:

{\ displaystyle \ Delta \ subseteq Q \ times (\ Sigma \ cup \ {\ varepsilon \}) \ times Q}

It must be ensured that in is not already present, but only represents the empty word. ${\ displaystyle \ varepsilon}$ ${\ displaystyle \ Sigma}$

NEAs with epsilon transitions cannot recognize more words than without this extension. For an NEA with epsilon transitions there is always an equivalent NEA without epsilon transitions. But you can simplify the construction of some machines. For example, one can construct an automaton for an NEA with little effort that accepts Kleene's envelope of the language of , that is . ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle {\ mathcal {A}} '}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle {\ mathcal {L}} ({\ mathcal {A}} ') = ({\ mathcal {L}} ({\ mathcal {A}})) ^ {*}}$

Multiple starting states

A NEA with a new start state that connects the start states of partial automations with epsilon transitions

It is also possible to allow several start states.

The automaton is then defined as having . ${\ displaystyle {\ mathcal {A}} = \ left (Q, \ Sigma, \ Delta, S, F \ right)}$ ${\ displaystyle S \ subseteq Q}$

Such automatons can be converted into NEAs with exactly one start state by means of transitions, by introducing a new state from which the original start states can be reached through transitions. ${\ displaystyle \ varepsilon}$ ${\ displaystyle \ varepsilon}$

In this way one can two machines a NEA create, whose language is the union of the languages of the other two machines, so . In the case of disjoint sets of states of and one only has to introduce a new start state which is connected to the start states of the two automata via epsilon transitions. The set of accepting states is the union of the accepting states of the two automata. ${\ displaystyle {\ mathcal {A}}, {\ mathcal {B}}}$ ${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle {\ mathcal {L}} ({\ mathcal {C}}) = {\ mathcal {L}} ({\ mathcal {A}}) \ cup {\ mathcal {L}} ({\ mathcal { B}})}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle {\ mathcal {B}}}$

properties

NEAs, DEAs and type 3 grammars (see Chomsky hierarchy ) describe the same language class . NEAs can be converted into equivalent DEAs using power set construction.

The main difference between the NEA and the deterministic finite automaton (DEA) lies in the fact that several subsequent states are possible or can be completely absent. However, these are not two different types, but a DEA is a special form of the NEA.

In order to convert a regular expression into an NEA, certain rules must be followed. This process is called inductive construction or Thompson's construction .

credentials

↑ Katrin Erk, Lutz Priese: Theoretical Computer Science: A Comprehensive Introduction. 3. Edition. Springer, 2008, ISBN 3-540-76319-8 , page 67
↑ Hans Werner Lang: http://www.inf.fh-flensburg.de/lang/theor/regulaerer-ausdruck-zu-automat-bottomup.htm
^ Alfred V. Aho , Ravi Sethi, Jeffrey Ullman : Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986

literature

John E. Hopcroft , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2nd Edition. Addison-Wesley , Bonn, Munich 1990, ISBN 3-89319-181-X (Original title: Introduction to automata theory, languages and computation .).
Peter Sander, Wolffried Stucky, Rudolf Herschel: Automata, Languages, Predictability. ISBN 3-519-02937-5
Gottfried Vossen , Kurt-Ulrich Witt : Basic course in theoretical computer science. 3. Edition. ISBN 3-528-23147-5

Web links

Article on the subject by Hans Werner Lang

[1] Katrin Erk, Lutz Priese: Theoretical Computer Science: A Comprehensive Introduction. 3. Edition. Springer, 2008, ISBN 3-540-76319-8 , page 67

[2] Hans Werner Lang: http://www.inf.fh-flensburg.de/lang/theor/regulaerer-ausdruck-zu-automat-bottomup.htm

[3] Alfred V. Aho , Ravi Sethi, Jeffrey Ullman : Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986