you know it's perfectly possible to construct valid regexes which won't terminate before all suns have burned out...

So your empirical approach is only practicable by limiting the regexes to a reasonable subset.

One thinkable way could be limiting to pure state machines and exploring feasible transits between states.

But this is highly speculative without a detailed question from the OP, IMHO it's a case of XY!