Non-deterministic finite automaton

Easy 25%

Non-deterministic finite automaton

We are used to drawing a automaton non-deterministic finite, by representing the states by circles, by indicating the initial state by an incoming arrow, the accepting states by a double circle or an outgoing arrow, and the transition from state q to state q' by reading the letter α by an arrow going from q to q' and labeled by α.

A non-deterministic finite 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 automaton transition function.

Note that a deterministic automaton is a particular case of a non-deterministic automaton which associates with any element of Q × Vt a part of Q having 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 be blocked, that is to say if there exists a state q and a letter a 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. So, for any 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 has however an essential consequence: there can be several derivations resulting from the initial state i which read a given word w, some of which can be blocked and others not, and in the latter case some can end in state accepting and others not. Acceptance takes place if there is at least one successful calculation. If all the calculations fail, there will be no other way to find out than to explore them all before knowing that the word w is not matched. The correct notion is therefore not that of calculation, but of a calculation tree associated with a word read by the automaton:

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

A derivation tree is constructed as in the case of a deterministic automaton. In the case of a non-deterministic finite automaton, it 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 iff one of the leaves of its calculation tree is labeled by an accepting state.

Non-determinism and recognized words

We consider the following non-deterministic finite automaton A = ({a, b}, {1, 2, 3}, ∆, {1}, {1}):

non-deterministic finite automaton

Is the word baabab accepted by automaton A?

non-deterministic finite automaton

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

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 of n.