Minimal DFA / regular expression from set of strings

user_21501 0
Viewed 118

I'm looking for an algorithm which produces the smallest DFA which matches any string from a given finite set of concrete strings, and nothing else. (Smallest as in fewest terminal symbols.)

Examples:

  • a, b -> a|b
  • a, ab -> a(|b)
  • ab, ac -> a(b|c)
  • aa, ab, ba, bb -> (a|b)(a|b)
  • x, xa, xb, xc, xac, xbc -> x(|ab)(|c)

I tried a naive algorithm which does repeated prefix/suffix extraction, but that cannot handle the last case, and does not produce the minimal result.

I'm sure this is a common problem but I haven't been able to find the proper terminology for it. Apologies for improper terminology and the ad-hoc notation.

formal-languages algorithm
1 Answers

Minimal DFA is pretty straightforward:

  1. Create an NFA which has one branch for each string in the language
  2. Determinize the NFA to get a DFA
  3. Minimize the DFA

Each of these steps is easy to understand and automate; steps 2 and 3 have known algorithms, step 1 should be easy too.

This is not a particularly efficient algorithm, but it might serve as a useful starting point. To improve performance, you'd want to try to build some DFA directly and then minimize that; perhaps running the Myhill-Nerode theorem as a construction could work here. But this is performance, not correctness... for small DFAs there will be no issue just running as above.

Minimal Regular Expression is a harder problem, I think; you could use Arden's lemma as a starting point to get some regular expression for the language of the DFA generated using the above described technique. Then, in the absolute worst case, you could check whether any valid regular expression of shorter length gives your language exactly. Note that because your language is finite and you want to match it exactly, your regular expressions will not have Kleene star in them, so this may not be as horrible as it sounds; the only operations remaining are concatenation and union. This might be feasible, if not terribly efficient. A lot of these options would probably be pretty easy to rule out; you know, for instance, you need at least as many concatenations as the longest string in your collection, so that gives an easy lower bound; there are probably tighter bounds you could find. The regular expression from Arden's lemma should give you a good upper bound.

user_8472690
Related