My teacher asked me to convert the regular expression $(a | b)^*$ to an NFA using Thompson's algorithm – well, I'm well aware of how this algorithm works, but since I'm not good at memorising details, I produced a slightly different NFA, and the teacher said it was wrong. Yeah, I know that it's not what the algorithm produces, but I guess it's not wrong either – what do you guys think?

This is the NFA that I produced: My NFA: 1-8, 1-2, 2-3, 2-4, 3-(a)-5, 4-(b)-6, 5-7, 6-7, 7-8, 8-1, 8 accepts

Thompson's algorithm produces an empty transition from state 7 to 2 instead of that from 8 to 1. Is there anything wrong with my construction? If so, could you please show me?

N.B.: The accepting state (8) is not marked because of a difficulty with the drawing tool.

  • 1
    $\begingroup$ You can check NFAs for equivalence by determinising and minimizing them. $\endgroup$ – Raphael Aug 26 '16 at 8:11

Your construction is correct, in that your FA accepts $(a\mid b)^*$. In fact, the construction is exactly the one that is used in a popular (and very good) text by Peter Linz. However, your instructor might have objected to the fact that it wasn't the one used in the Thompson paper, which of course it wasn't, as you noted. The upshot is that there are different, equivalent, ways of going from a regular expression to an NFA. As the sage said, "There are many roads to the top of the mountain, grasshopper".

(For instance, one might also propose the 1-state FA for this language, which also would be correct.)


As mentioned earlier, your NFA does accept $(a | b)^*$ but this does not correspond to the raw output Thompson's algorithm could produce.

Here is what I get:


  • $\begingroup$ This doesn't add anything over the question. $\endgroup$ – Raphael Aug 26 '16 at 8:10
  • $\begingroup$ After reading exact terms of the original question once again, you're right @Raphael , but I hope to satisfy curiosity of some curious readers giving the resulting Thompson's NFA. Hope this is not totally misplaced. $\endgroup$ – Adrien M. Aug 31 '16 at 19:34

Your Answer

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

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