> a 12,701 character regex for divisibility by 7:
I wonder if that's the optimal regex or can be reduced further using some rules[1] like the ones which we(humans) generally use to do it manually.
I wonder if that's the optimal regex or can be reduced further using some rules[1] like the ones which we(humans) generally use to do it manually.
(I have a regex -> DFA compiler here that I just threw your regex through. Seven states, connected as expected)
(I think I've read that finding the smallest one is not only NP-hard, but P-Space complete.)
Of (a \star b \star ) \star and ( a ∪ b ) \star, which is the canonical form? The transformation from the former to the latter is nontrivial as a \star b \star is not equivalent with a ∪ b.
It remains PSPACE-complete if you're given a corresponding DFA: "Jiang and Ravikumar [7] show moreover that the minimization problem for ... regular expressions remains PSPACE-complete, even when specifying the regular language by a dfa" from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60....
In that sense, the grandparent is incorrect. It is unknown, in both practice and theory, how to find the shortest equivalent regex.
Heck, there might be an algorithm that works really well in practice. People who do model checking and verification laugh PSPACE completeness in the face and are not even really concerned with undecidability.