in reply to
Re: Why machine-generated solutions will never cease to amaze me
in thread Why machine-generated solutions will never cease to amaze me
The proof for the (x?|y) case follows immediately from regex union being commutative.
Regexp union is not commutative when one of the alternates is a leading substring of another: then order becomes important - (E|x) will always match E in preference to x.
It is the presence of the outer anchors in the original pattern that disambiguates and thus makes it commutative.