Reduction rule for Kleene's Closure in replacement of Thompson's algorithm
Hi
I guess there must be people watching this list, interested in this.
I hope I now finally found the way I was looking for, to formulate a
reduction rule for Kleene's Closure which can be used in replacement
of Thompson's algorithm, or so I hope. I could be wrong about it,
however.
http://erik-poupaert.com/12001.html
If anybody feels like veryfying the reduction rule and the resulting
algorithm used to derive a regex DFA directly, feel free to let me
know what your results are.
The reduction rule is:
T{a(xy)*b} = T{ab} + T {axyb} + T{axyxyb}
With T{e} the collection of transitions derived from any regex e.
By applying the rule recursively, one obtains all DFA transitions for
any regex, or so I hope it is true. In such case, if proven to be
true, it is truly a replacement for Thompson's algorithm.
Greetings
Erik Poupaert
gcc-specific?
Hi In order to avoid being off-topic, does anybody know any mailing list where people discuss just algorithms specifically? It doesn't need to be compiler construction-specific -- even though they're amongst the most interesting algorithms around. I've recently devised an algorithm to produce user interfaces/paper forms for equipment inspection rounds. It eventually boils down to finding the largest continuous binary submatrix in a sparse binary matrix. Of course, it would be totally ridiculous is someone else described the algorithm already. I'd like to avoid that kind of embarrasment. The algorithm descends the problem's geometry stream in optimal order, and for each geometry searches the associated combinatorial stream. If someone knows of an interesting discussion place where people can verify each other's results, please let me know. Greetings Erik
