Strange behaviour

[reverofevil]

>>> print(parse("(\d{2})+") & parse("(\d{3})+") == parse("(\d{6})+"))
False

I don't see how \d(\d{6})*\d{5} differs from \d{6} (neither I see why it's computed to be a minimal regex).

[qntm]

Yeah, the two are equivalent:

>>> (lego.parse("(\\d{2})+") & lego.parse("(\\d{3})+")).equivalent(lego.parse("(\\d{6})+"))
True

but obviously that's not the minimal regex. In fact computing a minimal regex is insanely hard computationally, I believe. I don't know if there's an effective procedure for doing that.

I'll consider an extra reduction rule which can do that simplification.

[reverofevil]

@ferno The computationally hard (worst-case exponential) but easy to implement in greenery is Brzozowski's algorithm, where edges of DFA are reversed, resulting NFA is compiled into DFA, and then its edges are reversed once again. But nevertheless there're better alternatives. Hopcroft's algorithm is no harder than sorting, and (luckily) well covered in the "dragon book".

I didn't really expect == to behave differently from equivalent. Thank you!

[qntm]

Finding a minimal DFA using Brzozowski's algorithm is already part of greenery... but sadly a minimal DFA is not the same thing as a minimal regular expression! I don't know of any algorithm to find the latter. (Other than iterating over every possible regular expression in order of length.)

[reverofevil]

@ferno I forgot that you have to convert DFA back to regex somehow. I see it was totally my misunderstanding.

[reverofevil]

Well, it seems I still have some stupid questions to ask.

>>> (lego.parse("(\\d{2})+") & lego.parse("(\\d{3})+")).equivalent(lego.parse("(
\\d{6})+"))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'conc' object has no attribute 'equivalent'

[reverofevil]

Oh, please, update the version available in pip.

[qntm]

Yes, I will. Sorry, I got involved in a long series of breaking changes and new features (and bumped the version number) but then I never really finished them, so I never published the new stuff to pip.

[qntm]

Version 3.0 of greenery is now available on PyPI, this is the version which pip install greenery should retrieve for you next time.