On Sunday, July 24, 2016 at 3:45:40 PM UTC+5:30, Ben Bacarisse wrote: > Rustom Mody writes: > <snip> > > For a long time the re → dfa transformation went and was taught the > > laborious > > route: > > re → nfa-with-ε-transitions → nfa-without-ε-transitions → dfa > > > > https://en.wikipedia.org/wiki/Thompson's_construction > > https://en.wikipedia.org/wiki/Powerset_construction > > > > Now there is a direct, straightforward method which only becomes available > > (thinkable) when we have a null regular expression: > > https://drona.csa.iisc.ernet.in/~deepakd/fmcs-06/seminars/presentation.pdf > > "Now" seems an odd thing to say since the technique is quite old. It > would be better to say that it has been re-discovered.
The “Now” was not meant time-ly! > > But thanks for the link -- I was unaware of the idea. Unfortunately the > material is not well presented there (lower-case phi for the empty set?) > but in trying to understand what it was saying I found: > > https://www.cl.cam.ac.uk/~so294/documents/jfp09.pdf > > which, in my opinion, does it very much better. Yeah I think the one used when I was studying was this one http://www2.in.tum.de/hp/file?fid=571 Anyway my main point was that getting trivial cases right is damn hard And eliding the trivial case from a notation — because its too trivial to be useful is damn stupid -- https://mail.python.org/mailman/listinfo/python-list