Non-derterministic finite state automaton NFA

The automata are represented by displaying the states by circles, indicating the initial state by an incoming arrow, the accepting states by a double circle or an outgoing arrow, and the transition from the state q to the state q’ by reading the letter α by an arrow going from q to q’ and labeled by α.

A deterministic finite state automaton A is a triplet (Vt, Q, T) where

  • Vt is the vocabulary of the automaton;
  • Q is the finite set of states of the automaton;
  • T: Q × Vt → Q, is a partial application called the transition function.

Note that a deterministic automaton is a special case of non-deterministic automaton associating with any element of Q × Vt a part of Q possessing zero or one element (exactly one if it is a complete automaton). We can say of a deterministic automaton that it is incomplete if it can block, that is to say if there exists a state q and a letter such that T (q, a) = ∅. If it is complete, we have the following property:

Let A = (Vt, Q, T) be a complete non-deterministic finite automaton. Then, for every word u ∈ Vt and any state q ∈ Q, there exists a (not always unique) state q’∈ Q such that q(u) → Aq’.

The non-deterministic condition has an essential consequence: there may be several derivations from the initial state i that read a given word w, some of which may be blocked and some not, and in the latter case some may end in accepting state and others not. Acceptance occurs if there is at least one successful derivation . If all the derivations fail, there will be no other way to know it than to explore them all before knowing that the word w is not recognized. The good notion is not that of derivation , but of a derivation tree associated with a word read by the automaton:

Given a non-deterministic automaton A, the derivation tree with a root q ∈ Q generated by reading the word u is a doubly labeled tree defined by recurrence on u:
If u = ε, then the tree is reduced to its root q;
If u = av, the root q has outgoing transitions labeled a ∈ Vt to different derivation trees generated by the reading of v and whose roots are labeled by the states of T (q, a).

This process is not linear and can present various branches which will give various derivations leading or not to the recognition of the word.

A word u is recognized by a non-deterministic automaton A if one of the leaves of its derivation tree is labeled by an accepting state.

How to recognize words

We consider the following automaton A = ({a, b}, {1, 2, 3}, Δ, {1}, {1}):

langage7

Is the word baabab accepted by A?

langage8

No leaf corresponds to a final state, note that all leaves end in the bin.

Like the deterministic automaton, it is possible to construct the words recognized by the automaton by looking at the input lines and output columns. The words of lengths n are then constructed by raising the transition matrix to the power n.