MinDFA

For the purposes of this problem, a regular expression is defined by the following grammar:

<regex> ::= <letter> | '('<regex>')' | <regex>'|'<regex> | <regex>'*' | <regex><regex>
<letter> ::= a single lowercase letter ('a'-'z')

A regular expression is associated with a set of strings of lowercase letters, each of which we say matches the regular expression. To simplify the discussion, we will use the following notation:

 ε   the empty string
 ∃   there exists
 :   such that

Using this notation, we define matching as follows, where s is the string to match, and r is the regular expression to be matched.

Form of r |                              condition to match s
----------+-----------------------------------------------------------------------------
 r1r2     |  ∃ s1, s2 : s = s1s2, s1 matches r1, s2 matches r2
 r1|r2    |  s matches r1 OR s matches r2
 (r1)     |  s matches r1
 r1*      |  s = ε OR ∃ s1, s2 : s = s1s2, s1 matches r1, s2 matches r1*

Note that the '*' refers to the smallest regular expression to its left. Thus, the regular expression "abc*" is identical to "ab(c*)" and matches "ab" and "abccc", but not "abcabc". Furthermore, parentheses have the highest precedence, and '|' has the lowest. Here are some examples of regular expressions and some strings that match them:

regular expression | matching strings
-------------------+-----------------
 abc|a(abc)*       | abc, a, aabcabc
 a(ba)*|b(ab)*     | ababa, b, babab
 aa*bb*(ab)*|a*    | aaabababab, ab, ε

It turns out that every regular expression can be represented by a deterministic finite automaton (DFA). A DFA is a directed graph, whose nodes correspond to particular states, and whose edges correspond to particular letters. One of the states is denoted as the start state, and some subset of the states are denoted as accept states. For each letter in the string to be matched, starting from the first, a single edge is traversed, corresponding to a letter in the string (there may only be one outgoing edge from a node for a particular letter). If no edge corresponding to the a letter exists, then the string does not match the expression. If, after an edge has been followed for each letter in the string, the DFA ends up in an accept state, then the string matches, otherwise it does not. For example, the following diagram corresponds to the regular expression "aa*bb*(ab)*|a*", where nodes with a circle around them designate accept states, and the upper left node (with the incoming arrow from no other state) designates the start state.

Consider matching the string "aaabababab". If we start at the upper left node, and follow the edges, according to the characters in the string, we will eventually end up at the node in the center, which has a circle around it, and thus indicates that the string matches the regular expression. If, on the other hand, we try to match the string "abaa", we can see that we will reach the lower left node after "aba" and since there is no outgoing edge for 'a' at that node, the string does not match. Similarly, the string "aba" leaves us stranded at the lower left node, which does not have a circle around it, and hence does not match.

Your task is, given a regular expression, return the fewest states required of a DFA in order for it to represent the regular expression. For example, the above DFA happens to be minimal, so for the regular expression "aa*bb*(ab)*|a*" you would return 5.