I am trying to understand how the algorithm used by Flex works. I refer to the determinization procedure producing the output DFA. The algorithm is publicly available and contained in Flex's source code (dfa.c:345). However, I am experiencing several difficulties making out the idea behind it: this is mostly due to the fact the code has no (usable) documentation or meaningful variable names. What I know is that the algorithm revolves around equivalence classes to which states belong; their purpose is to speed up the DFA construction.

I tried to recover the paper by Vern Paxson where I thought the pseudocode of the algorithm would be but I had no luck. On page 4 the author points out the algorithm was challenging to design and that it might be part of future (post-1984) publications. I checked his publications but I think many of them went lost and I am currently unable to check them properly.

Is someone aware of an abstract description of the algorithm?

Can someone point out the title of a paper containing it, in case?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.