It is known that minimizing the size of a regular expression is PSPACE-complete even if we have a DFA as the language's specification.
What are the results if the language is finite?
One can consider this problem in two models:
- The input is all the strings in the language, and we measure the input size by the sum of the length of all strings.
- The input is a DFA, and we measure the input size by the number of states of the DFA.
Kleene star is not useful in the finite case, so only $()$, $|$ and $\cdot$(concatenation) are used in the expression. Of course, the length of a regular expression seems arbitrary. Instead, one can give weight to each operation(include adding parenthesis), and ask to minimize the weight of the regular expression.
Edit: As adrianN noted, it's related to grammar based codes. It's NP-complete to produce the minimum length context free grammar to describe a finite set. It's not clear why minimum size context free grammar can imply much about minimum size regular expression. Maybe a clever rewrite rule can related these two, and prove that in the first model, the problem is in NP.