Simulating a non-deterministic automaton

Suppose we have a non-deterministic automaton and want to find out whether it accepts a given string. We can convert the automaton to a deterministic one, we can try it somehow or we can use an algorithm that simulates the run of the NFA.

Principle of the algorithm

We will illustrate the principle on a suitable example. Take this automaton:

This is a non-deterministic finite automaton that accepts some language. We do not need to care which one right now. We will show what a computation of such an automaton looks like for the input string 11001. The idea is to process a symbol of the string and look at all the places we can reach thanks to multiple transitions for the same symbol. We remember all these states, and in the next step we assume that we are “in all of these states at once” and we are interested in where we can get to from them.

So we remember the set of states we may be in and the unread part of the string. At the start we have the pair ⟨{q₀}, 11001⟩. We start in state q₀ (the start state) and the input is the string 11001. The automaton looks like this, with the state we are in highlighted in red and bold:

The first symbol is 1, and from state q₀ there is only one transition for the symbol 1, so we get to state q₁. We remember the pair ⟨{q₁}, 1001⟩. The automaton looks like this:

We continue. The unread part of the string is 1001, so again we look for transitions for 1. There are two this time: back to state q₀ and on to state q₃. Now we go to both states at once. So we remember the pair ⟨{q₀, q₃}, 001⟩.

What is the logic of this? We know that there is a path from the start state, using the string 11, to state q₃ as well as to state q₀. We do not yet know which branch will turn out useful, so we simply remember both. We continue. The next input symbol is 0. Now we have to look at the transitions from q₀ as well as those from q₃. From state q₀ transitions lead to states q₁ and q₂, and from state q₃ a transition leads back to q₁. We include all these states, which gives the pair ⟨{q₁, q₂}, 01⟩:

But we are not finished with this step yet. We can see that an epsilon transition leads from state q₂ to state q₄. We know that we can take an epsilon transition “at any time” without reading another character. In other words, without reading the next symbol of the input string, we can still move to state q₄. So we add state q₄ to the states we may be in: ⟨{q₁, q₂, q₄}, 01⟩. We would colour the automaton like this:

Next the input is 0. We look at where we can move from the three states we are in. From q₁ we cannot move anywhere, because there is no transition for 0. The computation in this branch ends. From state q₄ we cannot get anywhere either. From state q₂ we get back to state q₂. But because an epsilon transition leads from q₂ to state q₄ again, we can get to state q₄ as well. So for the symbol 0 we can get from the set of states {q₁, q₂, q₄} to the set of states {q₂, q₄}, which gives the pair ⟨{q₂, q₄}, 1⟩:

Finally the input symbol is 1. From state q₂ we cannot get anywhere, so the computation in this branch ends. But from state q₄ we get to states q₃ and q₅. This gives the pair ⟨{q₃, q₅}, ε⟩:

The automaton has now read the whole string and is “in” two states: q₃, q₅. Because at least one of them is an accept state, the automaton accepts the string 11001.

The algorithm

First we need a function that takes a set of states as a parameter and works out which states we can still reach using epsilon transitions. The input is an automaton ⟨Q, Σ, δ, q₀, F⟩ and a set of states States, and the output is a superset of these states containing the states reachable using epsilon transitions. We call this operation the epsilon closure of the set States.

$$\begin{array}{r}\\ & \mathbf{Function}EpsilonClosure(⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩,States)\\ & NextStates\leftarrow \mathrm{\varnothing }\\ & \mathbf{ForEach}q\in States\mathbf{Do}\\ & NextStates\leftarrow NextStates\cup \left\{q\right\}\cup \delta (q,\epsilon )\\ & \mathbf{EndFor}\\ & \\ & \mathbf{If}NextStates\setminus States=\mathrm{\varnothing }\mathbf{Do}\\ & \mathbf{Return}States\\ & \mathbf{Else}\\ & \mathbf{Return}EpsilonClosure(⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩,NextStates)\\ & \mathbf{EndIf}\\ & \mathbf{EndFunction}\\ & \end{array}$$

We use this function inside the function that simulates the run of a non-deterministic automaton. The input is an automaton, an input string w = w₁w₂… w_n and the set of states the automaton is currently in. The output is either the answer Yes or No, depending on whether the automaton accepts the given string.

$$\begin{array}{r}\\ & \mathbf{Function}ComputeNFA(⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩,w,States)\\ & \mathbf{If}w=ϵ\mathbf{Do}\\ & \mathbf{If}States\cap F\ne \mathrm{\varnothing }\mathbf{Do}\\ & \mathbf{Return}\text{YES}\\ & \mathbf{Else}\\ & \mathbf{Return}\text{NO}\\ & \mathbf{EndIf}\\ & \mathbf{EndIf}\\ & NextStates\leftarrow \mathrm{\varnothing }\\ & \mathbf{ForEach}q\in States\mathbf{Do}\\ & NextStates\leftarrow NextStates\cup \delta (q,w_1)\\ & \mathbf{EndFor}\\ & NextStates\leftarrow EpsilonClosure(⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩,NextStates)\\ & \mathbf{Return}ComputeNFA(⟨Q,\mathrm{\Sigma },\delta ,q_0,F⟩,w_2{w}_3\dots w_n,NextStates)\\ & \mathbf{EndFunction}\\ & \end{array}$$

If we want to check whether the automaton accepts a string w, we call the function like this: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

Sources

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools