Suppose we have a regular language specified by a regex, for example, (ab|ac)* and we wish to find an equivalent regex with the minimal number of symbols, (a(b|c))*. Is there any efficient way to do this? From what I've read, minimizing the number of states in a DFA is easy, but minimizing a NFA is PSPACE-Complete, and I'm not sure which if either of these it falls under. If it's not tractable, are there any good approximation algorithms or special cases under which it can be done efficiently?
Note: By minimizing the number of symbols, I mean the number of times symbols in the alphabet (a,b,c in the example) appear in the regular expression. The number of parenthesis, | and *s don't matter.
Motivation - this idea comes from the challenge of minimizing program code size, given that if and while statements are the only allowable control flow. The possible paths through the control flow graph correspond to a regular language, with if being union, while being the Kleene star, and symbols representing primitive statements that don't transfer control.