Regex Gym Simplification Error

[PandaButts]

The Regex Gym won't simplify (a+ba*)* any further, but I believe it should simplify to just (a+b)*

[ibudiselic]

Thanks for getting in touch. I wouldn't say this is an error per se, it's
just that we don't have a rule that does this specific minimization.
Finding minimal length regular expressions is (I believe) PSPACE-hard so
what we do instead is implement a bunch of simplification rules that are
then applied. So we could add a rule like (A+BA_) => (A+B)_ for any
language pair A and B, but that still wouldn't minimize some other
"obviously non-minimal" regexes.

On Mon, Mar 28, 2016 at 10:45 AM, PandaButts [email protected]
wrote:

The Regex Gym won't simplify (a+ba_)_ any further, but I believe it
should simplify to just (a+b)*

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub
#9