NFA/DFA with variable transition conditions

Question

Good night,

Let's suppose I have a class which implements a NFA/DFA whose transitions are stored in a .NET Dictionary structure, and which takes an input word and recognizes a set of words derivable in some way from the input. Furthermore, let's suppose that the automaton is a generic template that can be applied to different words of the same length with only a re-labeling of the transition characters. What is the best way to encode the transition function in the Dictionary so that it's transitions can be re-labeled according to the input word's characters at runtime?

Thank you very much.

Answer 1

Please see the following implementation which takes an NFA and converts it to a DFA (and then to a graph) using a dictionary, just like yourself:

NFA to DFA

I am uncertain whether it has the dynamic relabeling capability you are seeking, but it is very well (in-line) documented, so you may get many ideas to help you with your project.

There is also a good (more recent) article on the topic of lambda transitions, but the image links of the article are no longer valid. However it does come with downloadable source code FSAutomata.zip that you can examine after reading the article:

NFA with Lambda Transition