# Thompson's Construction Algorithm produces a different NFA

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:

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.

• You can check NFAs for equivalence by determinising and minimizing them. – 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".
As mentioned earlier, your NFA does accept $$(a | b)^*$$ but this does not correspond to the raw output Thompson's algorithm could produce.