NFA with Lambda Transition

This semester I have a course about Automata, Formal Languages and Computability. It didn’t sound a good course for me at the beginning, but I after a while, I wished if I had this course before I did Compiler course back when I was doing my BCs. It was so hard for me to build a scanner for the compiler, we have had knowledge before though about FSA, but I think I didn’t grasp the whole picture back then.

Since the born of computer technology and the scientist haven’t and won’t stop searching for ways to simulate human minds. Recognition is one of these attempts, this field received so much attention for the last several  years, and have various fields such as string recognition, image recognition etc. FSA (Finite State Automata) was one of these attempts!!!

For this course, I have got to implement Nondeterministic Finite State Automation NFA-with Lambda transition, or sometimes called NFA-epsilon, for more information about NFA checkout Wikipedia.  Since there is a Lambda word in it I thought to use the new cool features in .NET 3.5, such LINQ, Extension Methods and especially Lambda Expression off course :)

My Implementation is fairly simple, if you are looking for more sophisticated and geeky code that uses C5 library then probably you might want to checkout Andrew Matthews Blog (NFA only, No lambda transition). The idea is quite simple; you have the following to consider:

  • Set of Alphabets.
  • Set of States (e.g. q1, q2 etc)
  • Start States.
  • Final States (Accepted States).
  • Transition Function  (From_State, Symbol, To_State).

Since  I’m about to  implement NFA with Lambda transition, I need first to build NFA then add lambda feature to it later.  So let’s get started and build NFA,

I tried to build NFA to be Generic class so you can use any the data structure you like. I extensively make use of the Generic class System.Collections.Generic.List; you might want to use some generic dictionaries that are implemented in C5 library to enhance the performance. For this demo I will stick to the  .NET framework and keep it simple.

For NFA we define the following, note here the generic type Q denote the state type and S denote symbol type. In NFA class we define

  • List to store the current states.
  • A Transition table that accepted the form.       [ State<Q>, S, State<Q>] == > (From_State, Symbol, To_State)
  • List of all states each states has a type.

  • List of all alphabets.

You might notice that start states and final states are missing here !!!

 We create them as properties, by saying hay give me all the states where the type is equals to start state using lambda Expression for instance

Generally, the most important methods in the NFA class are

  •  GetNextStates
  •  ConsumeInputSymbol
  •  ComsumeAllInputSymbols

Method: GetNextStates:

Here we use LINQ to to filter out the transition table and find the next states. Also note we marked the method as virtual because we will be overriding it when we implement the NFA-with Lambda class.

Method: ConsumeInputSymbol

 

Method: ComsumeAllInputSymbols


NFA with Lambda Transition:

As probably you can guess, the only thing need to be changed in the class NFA to accomidate lambda tranision is the method GetNextStates, so we first build the new class NFAWithLambda and have it extend (inherit from the class NFA) 

For this library I assumed that Lambda is represented by NULL and that’s why I have added the restriction where S: class to enfore anyone who use this library to supply a reference type for the symbol e.g string

Please refer to the code attached for reference to the implementation of the method GetNextStates in the NFAWithLambda.

Testing the code:

In the attachment you will find two applictions; one is a console and the other is UI based.

 

I will post here some code that shows how to test the library

 

Hope this Help,

3 Comments

  • Good Work, Nawaf!

    For extra credits you can do what I'm going to have to do - timed transitions. If no transition occurs within a period of time, then transition back to the previous state. I'll be using this to allow the option to have intermediate (pending) states between button click and the new state.

  • Thanks Andrew,

    That seems great option. Actually, I'm working on a workflow system that has a similar idea but for escalation purpose, where some transaction steps have a timeout, if fired then this pending transaction step gets escalated to a higher level as it’s defined in the workflow routing table or perhaps based on the Role, e.g. escalate to the manager, and something like that.

    There are other things we can think of, such as having set of criteria that define where to go, say if approved & payment > $1000 then go to step A. Or may be based on a percentage e.g. if 7 managers out of 10, approved the transaction step A then go to step B.

    But I think this goes beyond NFA, and specifically this is more established in BPEL and XPDL. Yet still NFA is just part of it.

    Thanks,

  • Yeah, it happens sometimes ... Nothing special.

Comments have been disabled for this content.