3 ms·
I think I got your point. It is valid. To construct the DFA and have a finite number of derivatives we have to keep track of the following equivalences: r + r
by c0nstantine 4y ago
I think I got your point. It is valid. To construct the DFA and have a finite number of derivatives we have to keep track of the following equivalences:
r + r ~ r
r + s ~ s + r
(r + s) + t ~ r + (s + t)
In [1] authors state this and refer to the proof in the original paper. They even extend it to a set of extended rules to reduce the number of terms (states) even more.
Actually, the code for (lazy) DFA construction code is not even committed yet. The repo contains just sequential per-character application of the derivative to a regex. Which is obviously finite (though not efficient). Again, just to demonstrate the concept.
[1] https://www.ccs.neu.edu/home/turon/re-deriv.pdf https://www.ccs.neu.edu/home/turon/re-deriv.pdf
- mananaysiempre 4y agoYes, and even if you aren’t constructing a DFA, only being able to produce a finite number of derivatives from a given RE is still useful: As there’s only a finite number of derivatives, their length is obviously bounded by a constant for a fixed starting RE (though that constant is still exponential in the length of that RE). This implies your non-DFA-based matcher can only take a bounded time computing the next derivative, so takes a time proportional to the length of a string to process that string (even if the constant of proportionality is exponential in the RE length). (I’m not good at fitting all of my reasoning into a single comment today, am I?)
- carapace 4y agoHey hey, FWIW I wrote this up too (also in Python but in a different style, and without as many cool glyphs): https://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expressions.html https://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expre... One neat thing is that the "compaction" rules to avoid exponential blowup are symmetrical (they form like, a ring or semi-ring or whatever, sorry I'm not a mathematician.) https://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expressions.html#compaction-rules https://joypy.osdn.io/notebooks/Derivatives_of_Regular_Expre...
- c0nstantine 4y agoHi, thanks for sharing. Didn't know there is a python implementation. Your article is broader and I like the functional flavor. For the 'compaction' you mention, yes it is useful. But the code will be more complicated and optimization wasn't the point of the sketch.