How to find out the maximum and minimum length of strings that match to a given regular expression

Question

A theoretical question. I have a regex. I want to find the strings that match to this. How can i get the minimum and maximum length of these strings?

Answer 1

Convert the regular expression to an NFA (with epsilon transitions, if you like). Delete every state that cannot reach an accepting state (this might be a no-op). The minimum length is the length of a shortest path to an accepting state (use Dijkstra from the start state, where transitions with symbols have length 1 and epsilon transitions have length 0). Using a double-ended queue, this is linear-time. The maximum length is infinity iff there is a cycle. Otherwise, the transition graph is acyclic; use an algorithm for longest path in an acyclic graph.