Unable to construct 4-state NFA for certain regular expression

Question

In an exercise on NFA's I'm asked to construct a 4-state NFA on the regular expression (aa|aab)*b. I have tried to construct it myself, and I could only find a 5-state NFA, which an online tool later confirmed.

(I found it without (4) being final and an additional arrow from (3) to (2) of b, but this results in the same) Is it me failing to see a problem, or isn't there a way to do this with just four states?

Answer 1

You've chosen to create a DFA (and I can't tell how to make one with only 4 states either). However, you are allowed to build an NFA, which means you can have multiple transitions with the same letter.

You could therefore omit state (2), move the b-edge that went from (0) to (2) onto (4), and introduce a new edge with the letter b from (3) to (0). This means that when reading a b after two as, you can either transition to the final state or back to the beginning.