izuzak
Regex Gym Simplification Error
The Regex Gym won't simplify (a+ba*)* any further, but I believe it should simplify to just (a+b)*
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 https://github.com/izuzak/noam/issues/9
