Detecting the trivial can be non-trivial (was Why not allow empty code blocks?)

[Ben Bacarisse]

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.