Conversion of nfa with self-loop to one without self-loop
Add a new state and make the self loop point to the new state and add a empty transition from the new state back to the original state.

It is straightforward to prove that this NFA is equivalent to the original.