Non-deterministic to deterministic automata (subset construction method)
by Tomás de Camino Beck

Introduction

In the theory of computing, automata theory is central to understand and analyze the behaviour of discrete systems. Not only an automata can be used to process and analytically study languages, but they can be used as a way of programming, or modelling machines.

The subset construction method, is a universal method for converting a non-deterministic finite automata to a deterministic one. The method not only does the conversion, but it is the foundation of proving the equivalence of these two kinds of automata, that is, that there is an equivalent DFA to every NFA. I talk about non-deterministic automata on this post, and deterministic ones on this one.

On this post I focus on constructing functions in Mathematica to apply this method. I assume that you have already some knowledge in Automata Theory.

Subset Construction Method

Here I will give a not so rigorous description of the method, for complete details have a look at Hopcroft & Ullman’s book. You can also check Ullman himself explaining on this video.

Given a NFA with states

, the method creates a power set



. Basically you have to get all the transitions from all sets constructed

S⊆

, for every symbol in the alphabet

. The transition function

is then defined as

(S,a)

⋃

p∈S

(p,a)

. Basically we have to calculate all the states than can be reached from the powerset

Time for Coding

Lets work with a simple (and classic) example. This is the same example that I used on this post.

Consider the following NFA, that accepts strings that end in 01 (initial state in white and final state in red),

Notice how, when in state 0 and receiving symbol “1”, the transition stays in state 0 but also goes to state 1. This is the transition table,

Out[]=

Q\Σ	0	1
0	{0,1}	{0}
1	-	{2}
2	-	-

Notice how, when in state 0 and receiving symbol “1”, the transition stays in state 0 but also goes to state 1. We define this NFA using the following association,

In[]:=

δ=Association[{0,"0"}{0,1},{0,"1"}{0},{1,"1"}{2}];

To compute a string with this automata, I have created the following extended (



) function for the non-deterministic automata,

In[]:=

DeltaHatNFA[δ_,q0_List,string_]:=FoldList[Union@@Table[δ[{#1[[i]],#2}]/._MissingNothing,{i,Length[#1]}]&,q0,Characters[string]]

We can now use it to evaluate the string “00101” for example,

In[]:=

DeltaHatNFA[δ,{0},"00101"]

Out[]=

{{0},{0,1},{0,1},{0,2},{0,1},{0,2}}

It should be clear from the output that the NFA, starts in state 0, receives symbol “0”, and it then moves to state 0 and state 1 at the same time. Then every state has to be evaluated when the next symbol comes.

First we create the powerset using the Subsets function. For the example (3 states) we have,

In[]:=

S=Subsets[{0,1,2}]

Out[]=

{{},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}}

Notice how the powerset has 8 combinations (

, where

is the number of states).

Now we have to calculate the transition for each element in

combined with each symbol (the union of each results). IN other words we have to create all the Keys we are going to evaluate in

. We can use the Outer function to do this, the following way,

In[]:=

newKeys=Flatten[Outer[{#1,#2}&,S,{"0","1"},1],1]

Out[]=

{{{},0},{{},1},{{0},0},{{0},1},{{1},0},{{1},1},{{2},0},{{2},1},{{0,1},0},{{0,1},1},{{0,2},0},{{0,2},1},{{1,2},0},{{1,2},1},{{0,1,2},0},{{0,1,2},1}}

Notice how we also flatten the result at level 1. With this, now we can evaluate

for each key,

In[]:=

newValues=Map[Union@@Table[δ[{#〚1,i〛,#〚2〛}]/._MissingNothing,{i,Length[#1]}]&,newKeys]

Out[]=

{{},{},{0,1},{0},{},{2},{},{},{0,1},{0,2},{0,1},{0},{},{2},{0,1},{0,2}}

Note that this execution will give you a warning because of son empty lists, but this doesn’t really cause problems.

Now we just have to combine them in a new association,

In[]:=

newDelta=AssociationThread[newKeysnewValues]

Out[]=

{{},0}{},{{},1}{},{{0},0}{0,1},{{0},1}{0},{{1},0}{},{{1},1}{2},{{2},0}{},{{2},1}{},{{0,1},0}{0,1},{{0,1},1}{0,2},{{0,2},0}{0,1},{{0,2},1}{0},{{1,2},0}{},{{1,2},1}{2},{{0,1,2},0}{0,1},{{0,1,2},1}{0,2}

We can now create a more general function for any NFA,

In[]:=

NFAtoDFA[δ_,nstates_,Σ_]:=AssociationThread[Flatten[Outer[{#1,#2}&,Subsets[Range[0,nstates-1]],Σ,1],1]Map[Union@@Table[δ[{#〚1,i〛,#〚2〛}]/._MissingNothing,{i,Length[#1]}]&,Flatten[Outer[{#1,#2}&,Subsets[Range[0,nstates-1]],Σ,1],1]]]

Not the most efficient since we are doing some things twice in the code (calculating keys), but I want to keep things in the functional domain, and for educational purposes. Let see if it works,

In[]:=

NFAtoDFA[δ,3,{"0","1"}]

Out[]=

Cleaning empty states

Now we can clean some of the empty states just by using the Select function,

In[]:=

newDelta=Select[NFAtoDFA[δ,3,{"0","1"}],#≠{}&]

Out[]=

{{0},0}{0,1},{{0},1}{0},{{1},1}{2},{{0,1},0}{0,1},{{0,1},1}{0,2},{{0,2},0}{0,1},{{0,2},1}{0},{{1,2},1}{2},{{0,1,2},0}{0,1},{{0,1,2},1}{0,2}

Removing non reachable states

To find the non reachable states, we look at the Values in our new transition function, and search in our powerset

for the new states that are not contained there.

In[]:=

NonReachableStates[δ_,nstates_]:=DeleteCases[Complement[Subsets[Range[0,nstates-1]],Union[Values[δ]]],{}]

So, for our example,

In[]:=

NonReachableStates[newDelta,3]

Out[]=

{{1},{1,2},{0,1,2}}

These are the states we have to eliminate. We use Outer to build the keys with the alphabet and eliminate them using KeyDrop,

In[]:=

EliminateKeys[δ_,Σ_,nstates_]:=KeyDrop[δ,Flatten[Outer[{#1,#2}&,NonReachableStates[δ,nstates],Σ,1],1]]

In[]:=

δ2=EliminateKeys[newDelta,{"0","1"},3]

Out[]=

{{0},0}{0,1},{{0},1}{0},{{0,1},0}{0,1},{{0,1},1}{0,2},{{0,2},0}{0,1},{{0,2},1}{0}

Notice that our new states are “{0}”,”{0,1}”, and “{0,2}”, these are not set of states anymore, but rather new labels for a state.

Here is the graph of our equivalent DFA,

Final states are in red, and initial state in white. Now we can apply a

for a deterministic automata, to the new

function. The DFA transition table,

Out[]=

Q\Σ	0	1
{0}	{0,1}	{0}
{0,1}	{0,1}	{0,2}
{0,2}	{0,1}	{0}

Now we can apply a

for a deterministic automata, to the new

function

In[]:=

DeltaHatDFA[δ_,q0_,string_]:=FoldList[δ[{#1,#2}]/._MissingNothing&,q0,Characters[string]]

In[]:=

DeltaHatDFA[δ2,{0},"0101"]

Out[]=

{{0},{0,1},{0,2},{0,1},{0,2}}

The NFA defined with

is equivalent to

constructed. The initial state of the DFA is the one that contains de initial state of the NFA, and the final states are the ones that contain any final state of the NFA.

Final Comments

The code can certainly be improved. For example you could do a “lazy” construction of the powerset, that is, working only the states that area reached, instead of creating all states and then erasing.

In the future I hope to build more examples using this procedure, and focused more on the language of the automata, rather than on the automata itself.

The goal here is not to create the perfect or smallest code, but rather to build a code that is closer to the mathematical definition of the method, and to use it as an educational tool for teaching Mathematica and Automata Theory. Please feel free to improve! Will post in the future functions for creating nice graphs and transition tables for different types of automata like the ones used here.

References

◼

Hopcroft and Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley.