Detecting the trivial can be non-trivial (was Why not allow empty code blocks?)
Ben Bacarisse
ben.usenet at bsb.me.uk
Sun Jul 24 06:15:24 EDT 2016
Rustom Mody <rustompmody at gmail.com> 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.
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.
<snip>
--
Ben.
More information about the Python-list
mailing list