Nondeterministic finite automaton

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

Definition

Formally, a NEA be defined as a 5-tuple. Where:

• Is a finite set of states ().
• Is the input alphabet.
• Is the transition relation (or transition relation ).
• Is the start state.
• Is a (finite ) set of possible accepting states (final states). When the machine stops in a state of after reading the input word, as part of the language.

Behavior

Reads the NEA in a state of the input symbol, the switch will not deterministic in a successor state, which is given by the transition relation. So the machine has the choice between all states, applies.

There is no such condition, the machine stops prematurely and discards the input.

An input word is considered to be accepted if there is a by given sequence of state changes, in which the machine does not stop prematurely and the last state is an accepting state.

Transition as a function

Alternatively, the transitions defined by a transition function, which then maps to a set of states:

Since the function can also map to the empty set, so that it can apply a premature stopping is also possible here.

Epsilon transitions

One can also define NEAs so that state transitions are possible in which no input signal is read. Before or after reading a character, a NEA can therefore randomly change state. The conditions that can be changed are connected by transitions that read instead of a symbol the empty word (sometimes ). This change of state is called transitions or steps. In graphical representations of NEAs transitions than (or) labeled edges are represented and therefore also called edges.

Formal enables you these transitions by extending the transition relation:

It must be ensured that it is not in there already, but only represents the empty word.

NEAs with epsilon transitions can not recognize more words than without this extension. There is an NFA with epsilon transitions thus always an equivalent NFA without epsilon transitions. However, you can simplify the construction of many machines. For example, one can construct an NFA with little effort an automaton that accepts the language of Kleene'sche shell, ie.

Several initial states

It is also possible to allow a plurality of start conditions.

The machine is then defined as having.

Such machines can be converted by means of transitions in NEAs with exactly one start state by introducing a new state from which you can reach the original starting states through transitions.

In this way one can create an automatic two NEA, whose language is the union of the languages ​​of the other two machines, ie. For disjoint sets of states of and you have to introduce only one new start state, which is connected via epsilon transitions with the initial states of the two machines. The set of accepting states is the union of the accepting states of the two machines.

Properties

NEAs, DEAs and type-3 grammars ( cf. Chomsky hierarchy ) describe the same class of languages ​​. NEAs can be converted by means of the power set design in equivalent DEAs.

The main difference of the NEA to the deterministic finite automaton (DFA ) is thus that several sequelae are possible or can be completely absent.

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