Non-deterministic finite automaton

The finite automaton from the previous chapters (we call it an FA or DFA) was always deterministic, which means that at every moment it was clear what the automaton would do. Now we will look at the more general concept of non-deterministic finite automata (NFAs), in which several transitions can leave the same state for the same symbol.

Example

Look at the following diagram of an automaton:

What is unusual about it? Two edges for the symbol 0 leave the node q₀. If we try to accept the string 001, the automaton seems not to know whether it should stay in state q₀ or follow the transition to q₁. Such an automaton is non-deterministic.

Determinism in this sense means that in every situation it is clear what the automaton will do, with no room for ambiguity. A deterministic automaton has exactly one transition for each state and each symbol. Non-determinism means ambiguity: from one state there may be, say, three transitions for the same symbol.

So how does the automaton decide? A non-deterministic automaton always chooses (we sometimes say “guesses”) the transition that leads to accepting the string, if that is possible.

If we feed the string 001 into the automaton, it has these ways of processing it:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

plus the ways in which it does not read the whole string. In the first one it stays in state q₀ all the time, which it certainly may, because the transition rules allow it. In the second branch it ventured into further states and finally reached state q₂, which is an accept state. In this branch the automaton would accept the string. A non-deterministic automaton automatically chooses the branch in which it accepts the string, if such a branch exists.

How does it automatically choose the “favourable” branch? We can imagine that the non-deterministic automaton goes through all the possible branches, and if it finds a branch in which it accepts the string, then it accepts the string. How could it go through all the branches? Put simply, whenever it is in a state with n edges for the current symbol, the automaton copies itself n times and each copy goes a different way. This way we gradually go through all the possibilities.

Tree representation of a computation

Let’s modify the previous automaton slightly:

The non-determinism stays in the first state. The previous automaton accepted all strings that end with 01. This modified automaton accepts all strings that contain the substring 01. So it accepts, for example, the strings 101 and 0101. We can easily visualise all the branches of a computation using a tree. For the string 01010 the tree could look like this:

At the start we are in the start state q₀. The input is the string 01010 and the first unread character is 0. Two transitions for the symbol 0 leave state q₀, to states q₀ and q₁. So the tree has two children at this node: q₀ and q₁. Next we read the symbol 1. There is no ambiguity there, and we move to states q₀ and q₂. Then we read the character 0, and in the left branch there is ambiguity again, so we split the computation into two more branches. In one we stay in q₀ again, and in the other we go to q₁. And so on.

Notice that two branches in total end in state q₂, an accept state. There are two branches of the computation by which the automaton can accept the string. So this automaton would accept the string 01010. We can try to build a similar tree for the string 1000.

The computation either stays in state q₀ or moves to state q₁, but from there it has nowhere to go, because the rest of the input is all zeros and state q₁ has a transition only for the symbol 1. No branch of the computation ends in an accept state, so the automaton does not accept the string 1000.

Epsilon transitions

In non-deterministic automata we can also use epsilon transitions. These are transitions that we can take whatever symbol is on the input, without reading any symbol of the string. How could we write a non-deterministic automaton that accepts the empty string, all strings consisting only of 1s and strings of the form (10)ⁿ, that is 10, 1010, …?

We have split the automaton into two “sub-automata”. The upper one recognises the strings consisting of 1s, and the lower one handles the strings of the form (10)ⁿ. Let’s try to accept the string 111. At the start the automaton is in state q₀ and the input is the string 111. Because epsilon transitions are available, it can decide to move to state q₁ or q₂, whichever suits it. We can see that moving to state q₁ will suit it. The automaton moves there. Meanwhile the input is still the string 111! Only now does it start reading symbols of the string and moving from q₁ to q₁ again, until it has read the whole string and accepts it.

If we tried to accept 1010, the automaton would move to state q₂ at the start, and only from there would it start processing symbols, and again it would accept the string.

For the string 1100 the automaton could do anything, because it has no way to accept it.

Epsilon transitions and non-determinism make our work much easier in many ways. For example, the proof that the union of regular languages is again a regular language can be written much more simply with epsilon transitions than in the case of deterministic finite automata. In that proof we had examples of these automata

and

and then we constructed a deterministic finite automaton that accepted the union of both languages. With epsilon transitions we can build such an automaton like this:

We simply add a new start state, and from it two epsilon transitions lead to the original start states of the original automata, and that is all. The automaton decides non-deterministically whether to try to accept the string with one “sub-automaton” or the other.

Definition of a non-deterministic automaton

We have already shown how a deterministic and a non-deterministic finite automaton differ, so it only remains to formalise it. We defined a deterministic finite automaton as a 5-tuple ⟨Q, Σ, δ, q₀, F⟩, where Q is the set of states, Σ is the alphabet, δ is the transition function, q₀ is the start state and F is the set of accept states. The only thing that changes in the definition of non-deterministic automata is the definition of the transition function.

In the deterministic version the function call δ(q, w) could return only one state, whereas in the non-deterministic version it can return several states, if several transitions are defined for one symbol. Because we also need to define epsilon transitions, we denote the set Σ ∪ {ε} by Σ_ε, that is Σ_ε = Σ ∪ {ε}. We define the function δ as

$δ : Q \times Σ_{ε} \to 2^{Q}$

Here 2^Q denotes the power set, the set of all subsets of Q. The formalisation of a computation is very similar to that for finite automata. A configuration of the automaton is again a pair ⟨q, w⟩ ∈ Q × Σ^∗. A computation step ↦ is a relation on the set of configurations such that

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

if and only if q_j ∈ δ(q_i, w₀). This sentence contains the biggest difference. In deterministic automata we wrote this condition as q_j = δ(q_i, w₀), because the function δ always returned one state. The non-deterministic version of the transition function returns a set of states, which is why the symbol ∈ appears. We will again denote the reflexive and transitive closure of the relation by ↦ ^∗. We say that the automaton accepts a string w if and only if there exists q_f ∈ F such that

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

Sources

Chapters: Finite-state machine, Complete automaton, Non-deterministic finite automaton, Simulating a non-deterministic automaton, Converting an NFA to a DFA

« Previous: Complete automaton

Next: Simulating a non-deterministic automaton »