Nondeterministic Finite Automaton (NDFA) in C#

Download the source: Example 1.

Sad to say, but my holidays are over, and I’m back to work. I tried pretty hard to keep my hands away from the laptop while I was off, but I got itchy fingers towards the end so I had a stab at implementing a non-deterministic finite automaton (NDFA). I implemented it to give me an excuse to play with the C5 collections library. As it turned out the class was relatively easy to implement as a deterministic finite automaton (DFA) but required a bit more finesse to extend it to the general case of the NDFA. Anyhow I got it working OK. Here’s how you might use it:

<span class="lnum"></span>

<span class="lnum">   1:  </span>NDFA<QState, <span class="kwrd">char</span>, <span class="kwrd">string</span>> ndfa = <span class="kwrd">new</span> NDFA<QState, <span class="kwrd">char</span>, <span class="kwrd">string</span>>();

<span class="lnum">   2:  </span>ndfa.AllStates.AddAll(<span class="kwrd">new</span> QState[] { QState.err, QState.q0, QState.q1, QState.q2 });

<span class="lnum">   3:  </span>ndfa.AcceptStates.AddAll(<span class="kwrd">new</span> QState[] { QState.q2});

<span class="lnum">   4:  </span>ndfa.StartState = QState.q0;

<span class="lnum">   5:  </span>ndfa.ErrorState = QState.err;

<span class="lnum">   6:  </span>ndfa.SetStateComparer(<span class="kwrd">new</span> QStateComparer<QState>());

<span class="lnum">   7:  </span>ndfa.SetErrorHandler(<span class="kwrd">delegate</span> { Debug.WriteLine(<span class="str">"Error State Entered"</span>); });

<span class="lnum">   8:  </span> 

<span class="lnum">   9:  </span>ndfa.TransitionTable.Add(<span class="kwrd">new</span> Rec<QState, <span class="kwrd">char</span>>(QState.q0, <span class="str">'a'</span>), QState.q1);

<span class="lnum">  10:  </span>ndfa.TransitionTable.Add(<span class="kwrd">new</span> Rec<QState, <span class="kwrd">char</span>>(QState.q0, <span class="str">'a'</span>), QState.q2);

<span class="lnum">  11:  </span>ndfa.TransitionTable.Add(<span class="kwrd">new</span> Rec<QState, <span class="kwrd">char</span>>(QState.q1, <span class="str">'b'</span>), QState.q3);

<span class="lnum">  12:  </span>ndfa.TransitionTable.Add(<span class="kwrd">new</span> Rec<QState, <span class="kwrd">char</span>>(QState.q2, <span class="str">'b'</span>), QState.q3);

<span class="lnum">  13:  </span> 

<span class="lnum">  14:  </span>TransitionFunction<QState, <span class="kwrd">char</span>, <span class="kwrd">string</span>> func =

<span class="lnum">  15:  </span>    <span class="kwrd">delegate</span>(INdfa<QState, <span class="kwrd">char</span>, <span class="kwrd">string</span>> idfa, QState q, QState qn, <span class="kwrd">char</span> i)

<span class="lnum">  16:  </span>    {

<span class="lnum">  17:  </span>        <span class="kwrd">if</span> (idfa.IsErrorState)

<span class="lnum">  18:  </span>            <span class="kwrd">return</span> <span class="str">"Error Occurred."</span>;

<span class="lnum">  19:  </span>        <span class="kwrd">return</span>

<span class="lnum">  20:  </span>            <span class="kwrd">string</span>.Format(<span class="str">"Transitioned from {0} to {1} because of input '{2}' ({3})"</span>, q,

<span class="lnum">  21:  </span>                          qn, i, idfa.IsInAcceptState ? <span class="str">"Accept State"</span> : <span class="str">"Non-Accept State"</span>);

<span class="lnum">  22:  </span>    };

<span class="lnum">  23:  </span> 

<span class="lnum">  24:  </span>ndfa.TransitionFunctions.Add(<span class="kwrd">new</span> Rec<QState, QState>(QState.q0, QState.q1), func);

<span class="lnum">  25:  </span>ndfa.TransitionFunctions.Add(<span class="kwrd">new</span> Rec<QState, QState>(QState.q0, QState.q2), func);

<span class="lnum">  26:  </span>ndfa.TransitionFunctions.Add(<span class="kwrd">new</span> Rec<QState, QState>(QState.q1, QState.q3), func);

<span class="lnum">  27:  </span>ndfa.TransitionFunctions.Add(<span class="kwrd">new</span> Rec<QState, QState>(QState.q2, QState.q3), func);

<span class="lnum">  28:  </span> 

<span class="lnum">  29:  </span><span class="kwrd">foreach</span> (<span class="kwrd">string</span> output <span class="kwrd">in</span> ndfa.ProcessInput(<span class="str">"ab"</span>.ToCharArray()))

<span class="lnum">  30:  </span>{

<span class="lnum">  31:  </span>    Debug.WriteLine(output);

<span class="lnum">  32:  </span>}

Example 1: Using the NDFA

This sample implements a simple state machine that diverges into two states and then converges back into a single accepting state:

being a generic class it can work as well with chars, ints or enums for the state. My example above uses a simple enum called QState, plus a comparator to allow states to be stored in an ordered tree collection to allow quick state transitions:

<span class="lnum">   1:  </span><span class="kwrd">public</span> <span class="kwrd">enum</span> QState : <span class="kwrd">int</span>

<span class="lnum">   2:  </span>{

<span class="lnum">   3:  </span>    err,

<span class="lnum">   4:  </span>    q0,

<span class="lnum">   5:  </span>    q1,

<span class="lnum">   6:  </span>    q2,

<span class="lnum">   7:  </span>    q3

<span class="lnum">   8:  </span>}

<span class="lnum">   9:  </span> 

Example 2. The states used by the NDFA

The Rec<A,B> class is a record class (tuple) that is defined in C5 for associative containers such as dictionaries. I based my comparer on Rec<Q,Q> because I needed it to order the transition table which stores the one to many mappings from state to state.

<span class="lnum">  10:  </span><span class="kwrd">public</span> <span class="kwrd">class</span> QStateComparer<Q> : IComparer<Rec<Q, Q>>

<span class="lnum">  11:  </span>{

<span class="lnum">  12:  </span>    <span class="kwrd">public</span> <span class="kwrd">int</span> Compare(Rec<Q, Q> x, Rec<Q, Q> y)

<span class="lnum">  13:  </span>    {

<span class="lnum">  14:  </span>        <span class="kwrd">int</span> a = (13 * Convert.ToInt32(x.X1)) + Convert.ToInt32(x.X2);

<span class="lnum">  15:  </span>        <span class="kwrd">int</span> b = (13 * Convert.ToInt32(y.X1)) + Convert.ToInt32(y.X2);

<span class="lnum">  16:  </span>        <span class="kwrd">return</span> a - b;

<span class="lnum">  17:  </span>    }

<span class="lnum">  18:  </span>}

Example 3. A comparer to allow QState to be used with the C5 TreeSet, HashBag and HashDictionary collections.

In example 1, line 14, I use an anonymous delegate to create a ‘transition function’. Sorry to use contradictory terminology - transition function is a term used to describe the function that is used to find the next state to be transitioned to. In my case though I have augmented the NDFA to allow a delegate to be invoked as each transition is made. This allows the NDFA to do useful work as it goes. In the case of the function on line 14, it just says what happened to cause the transition, without doing anything.

Dialogue & Discussion