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.

  • $\begingroup$ what about converting some symbol strings to new symbols? does it have a meaning in your context? disallowed? it would seem to be equivalent to refactoring a particular path into a subroutine? this sounds similar to a compiler code optimization problem... $\endgroup$
    – vzn
    Aug 20 '12 at 18:55
  • 4
    $\begingroup$ I read only the abstract, but perhaps this paper is relevant: Minimizing NFA's and Regular Expressions. In particular: "... Jiang and Ravikumar [7] show moreover that the minimization problem for nfa's or regular expressions remains PSPACE-complete, even when specifying the regular language by a dfa ..." $\endgroup$ Aug 20 '12 at 23:33
  • 1
    $\begingroup$ Relevant information: en.wikipedia.org/wiki/… $\endgroup$ Aug 21 '12 at 0:20
  • 1
    $\begingroup$ I think that regexes are not a suitable representation for program minimization after all. Working with the control flow graph directly is easier. $\endgroup$
    – Antimony
    Aug 21 '12 at 21:07
  • 1
    $\begingroup$ As you said, I think the control flow chart is more suitable for your needs. Would it work to treat the graph as a DFA, and run known DFA state minimization algorithms on it in order to identify removable states ? EDIT : sorry, this should really be a comment but, being a noob, I can only post answers $\endgroup$ Aug 22 '12 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.