5
$\begingroup$

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of states?

For instance, consider this example. I have the regular expression $(a|b)$. According to this website, Thompson's algorithm converts it to the following NFA:

   o--->o
  /ε  a  \ε
>o        O
  \ε  b  /ε 
   o--->o

However, the following NFA is smaller and seems like it would also be equivalent:

   o
 a/ \ε
>o   O
 b\ /ε 
   o

Why doesn't Thompson's algorithm output the latter NFA? What did I miss here? Is that Thompson's construction algorithm not optimized at all?

$\endgroup$
4
  • 2
    $\begingroup$ Two possible explanations. 1. The algorithm might not produce optimal automata because it's easier to prove that it's correct, that way. 2. The epsilon transitions might be necessary (or at least helpful) when handling more complex regular expressions. Also, your reduced automaton still isn't optimal: you just need a start state and an end state, with an a transition and a b transition between them. $\endgroup$ Jun 22, 2015 at 21:16
  • 4
    $\begingroup$ You didn't miss anything except for the fact that there is no guarantee that Thompson's algorithm will produce a minimal FA. $\endgroup$ Jun 22, 2015 at 21:19
  • $\begingroup$ @RickDecker So when I compile an expression in Perl or whatever, will my compiler expression be the optimal one? $\endgroup$
    – nowox
    Jun 22, 2015 at 21:20
  • 1
    $\begingroup$ For most practical purposes, you want a DFA, anyway. The size of the minimal DFA is independent of the input NFA, and may blow up exponentially while the NFA generated by this algorithm is "small" relative to the input regular expression. So, considering the whole toolchain, I don't think we care too much about whether the NFA we get here is optimal. (Even if we could get it without large additional cost, why should we?) $\endgroup$
    – Raphael
    Jun 23, 2015 at 14:20

4 Answers 4

5
$\begingroup$

I had this same doubt when I was studying the Thompson's construction. As I see I am not the only one, I will try to solve the mystery.

Consider the regular expression: $$(a|b)|(c|d)$$

With Thompson's construction we generate first:

enter image description here

and then

enter image description here

Now let's use the noxwox's construction that you suggested. First we have:

enter image description here

And finally:

enter image description here

Can you see the difference? I had a first suspicion watching these two results. Then I reviewed the Thompson's constructions and I noticed something interesting. We can see the NFAs as directed graphs and the Thompson's construction guarantees a graph whose nodes have at most two successors.

So here starts my conclusion: Generating the data structure to store a NFA obtained by Thompson's construction is very easy because it is a set of nodes with two pointers each. If we use nowox's construction we don't know a priori the numbers of successors of each node and we have to change dynamically the amount of memory reserved for each node or be inefficient in the memory management. From this point of view the Thompson's construction algorithm guarantees a graph that is easy and fast to generate in a computer and I think that the additional computational cost of having more states than the NFA generated by nowox's construction is overshadowed by the backtracking mechanic of the NFAs.

$\endgroup$
11
$\begingroup$

Minimizing NFAs is known to be PSPACE-hard: Meyer and Stockmeyer showed that given an NFA, it is PSPACE-hard to find the size of the minimal equivalent NFA, and Jiang and Ravikumar showed that given a DFA, finding the size of the minimal equivalent NFA is PSPACE-hard. Later some hardness of approximation results were proved, showing that it is even hard to approximate the size of the minimal equivalent NFA. See these lecture notes by Artem Kaznatcheev for more details.

Since a regular expression can be converted to an NFA of comparable size using Thompson's algorithm, these hardness results show that we can't expect any efficient algorithm to convert an regular expression to a minimal-size NFA.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the lectures. It is very interesting $\endgroup$
    – nowox
    Jun 23, 2015 at 19:41
5
$\begingroup$

Thompson's algorithm has no chance to output an optimal NFA, simply because a regular language can be given by several different regular expressions. Just try the regular expression $(a + b)^*(a + b)^*(a + b)^*$ on the tool given in reference. You will end up with a 22-state NFA, very far from the optimal 1-state NFA.

$\endgroup$
4
  • $\begingroup$ Hmm. Why does the fact that a regular language has multiple different regexps mean that Thompson's algorithm can't output an optimal NFA? A hypothetical algorithm could plausibly output the optimal NFA for all of them (this would mean there are multiple inputs, multiple regexps, that all yield the same output, but that's not a contradiction or impossibility). In fact, one can even build an algorithm with this property, if you don't demand efficiency. I think one needs to know some additional properties of Thompson's algorithm for this reasoning to show it can't always yield an optimal NFA. $\endgroup$
    – D.W.
    Jun 23, 2015 at 7:38
  • 2
    $\begingroup$ Presumably the key point is that Thompson's algorithm is injective: if you have two (syntactically) different regexps $R_1,R_2$, then running Thompson's algorithm on $R_1$ yields a different NFA than running Thompson's algorithm on $R_2$. Is that the idea? Is this even true? It sounds plausible, but the proof of it seems not entirely trivial. $\endgroup$
    – D.W.
    Jun 23, 2015 at 7:41
  • $\begingroup$ Take any regular expression $R$ and then $()^*R$ on the given tool. $\endgroup$
    – J.-E. Pin
    Jun 23, 2015 at 7:51
  • $\begingroup$ @D.W. I think you can uniquely reconstruct the regular expression from the resulting automaton, so I think the proof is not too hard. $\endgroup$
    – Raphael
    Jun 23, 2015 at 12:44
2
$\begingroup$

The minimal NFA for an regular expression (a|b) as you described would be below:

    a, b
>o ------> O

Basically this automaton can be produced by Antimirov's construction based on partial derivatives of regular expressions. For this construction you need a procedure to determine the equivalence of two regular expressions, which is known to be hard (Sorry no magic here!). However, if you relax the absolute minimality guarantee, you can use a procedure determining similarity of two regexs, which is efficient, so you can construct a near-minimal NFA.

A starting point for derivatives of regular expressions can be found here: http://www.mpi-sws.org/~turon/re-deriv.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.