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:
1: NDFA<QState, char, string> ndfa = new NDFA<QState, char, string>();
2: ndfa.AllStates.AddAll(new QState[] { QState.err, QState.q0, QState.q1, QState.q2 });
3: ndfa.AcceptStates.AddAll(new QState[] { QState.q2});
4: ndfa.StartState = QState.q0;
5: ndfa.ErrorState = QState.err;
6: ndfa.SetStateComparer(new QStateComparer<QState>());
7: ndfa.SetErrorHandler(delegate { Debug.WriteLine("Error State Entered"); });
8:
9: ndfa.TransitionTable.Add(new Rec<QState, char>(QState.q0, 'a'), QState.q1);
10: ndfa.TransitionTable.Add(new Rec<QState, char>(QState.q0, 'a'), QState.q2);
11: ndfa.TransitionTable.Add(new Rec<QState, char>(QState.q1, 'b'), QState.q3);
12: ndfa.TransitionTable.Add(new Rec<QState, char>(QState.q2, 'b'), QState.q3);
13:
14: TransitionFunction<QState, char, string> func =
15: delegate(INdfa<QState, char, string> idfa, QState q, QState qn, char i)
16: {
17: if (idfa.IsErrorState)
18: return "Error Occurred.";
19: return
20: string.Format("Transitioned from {0} to {1} because of input '{2}' ({3})", q,
21: qn, i, idfa.IsInAcceptState ? "Accept State" : "Non-Accept State");
22: };
23:
24: ndfa.TransitionFunctions.Add(new Rec<QState, QState>(QState.q0, QState.q1), func);
25: ndfa.TransitionFunctions.Add(new Rec<QState, QState>(QState.q0, QState.q2), func);
26: ndfa.TransitionFunctions.Add(new Rec<QState, QState>(QState.q1, QState.q3), func);
27: ndfa.TransitionFunctions.Add(new Rec<QState, QState>(QState.q2, QState.q3), func);
28:
29: foreach (string output in ndfa.ProcessInput("ab".ToCharArray()))
30: {
31: Debug.WriteLine(output);
32: }
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:
1: public enum QState : int
2: {
3: err,
4: q0,
5: q1,
6: q2,
7: q3
8: }
9:
10: public class QStateComparer<Q> : IComparer<Rec<Q, Q>>
11: {
12: public int Compare(Rec<Q, Q> x, Rec<Q, Q> y)
13: {
14: int a = (13 * Convert.ToInt32(x.X1)) + Convert.ToInt32(x.X2);
15: int b = (13 * Convert.ToInt32(y.X1)) + Convert.ToInt32(y.X2);
16: return a - b;
17: }
18: }
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.
Industrial Inference 