12

Does anyone know of any good NFA and DFA implementation in C#, possibly implementing as well conversions between both? What I would like would be to be able to construct a NFA and then convert it automatically to a DFA, but without having to write my own code which would take a very long time. There is this Python code which perhaps I could use and integrate with C# using IronPython, but Python is slow.

rene
  • 41,474
  • 78
  • 114
  • 152
Miguel
  • 3,466
  • 8
  • 38
  • 67
  • Looking that the python code, it should be relatively easy to convert to C#. Have you considered doing that? – Jeff Mercado Oct 23 '10 at 21:56
  • The question is that I understand nothing about Python... – Miguel Oct 23 '10 at 22:02
  • Slow is relative... anyway, the NFA->DFA algorithm is rather trivial (with some general caveats in general) and is a topic of many Junior CS Automata-Theory courses -- I had to do this :) There any many good links off of "convert NFA to DFA" on google. Look at those relating to courses in particular. It should be less than a day of coding; perhaps only a few an hour or two and likely less painful than trying to hopscotch through different languages. –  Oct 23 '10 at 22:15
  • The algorithm to convert NFAs to DFAs is exponential in the number of NFA states in the worst case, so... slow is not going to be a phenomenon due to Python. – Patrick87 Aug 17 '11 at 13:12
  • You may also want to look at project Fare. http://stackoverflow.com/questions/5841454/convert-nfa-to-dfa/8240209#8240209 – Nikos Baxevanis Nov 23 '11 at 10:54

1 Answers1

21

Take a look at my series of posts about this subject:

Regular Expression Engine in C# (the Story)

Regex engine in C# - the Regex Parser

Regex engine in C# - the NFA

Regex engine in C# - the DFA

Regex engine in C# - matching strings

Leniel Maccaferri
  • 100,159
  • 46
  • 371
  • 480
  • 1
    I would like to use your code, but it does not have a license listed. If you are ok with people using it, would you distribute a version with an explicit license? – Ethan Reesor Aug 03 '15 at 23:36
  • 1
    @FireLizzard you can use it the way you want. In my blog I have included a Creative Commons badge right below my G+ profile. :) Feel free to use the code. – Leniel Maccaferri Aug 03 '15 at 23:48