Finding an automaton with a given number of states Define an NFA with 4 states that is equivalant to the following Regular Expression. $(01 + 011 + 0111)^*$.


My main problem is that to check for a string of length 4 (0111) I need at least 5 states to begin with. So to my (novice) little brain the question seems wrong.
Hint: for 0111 you need 4 transitions (one for each input letter). If you have a sequence of 5 separate states (which is probably your first try), than you will have 4 transitions between them. However, if you have 4 states connected in a circle, you will also have 4 transition between them...