# Conversion of nfa with self-loop to one without self-loop

For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent NFA that does not have any self-loop. How can we prove this statement in a general basis without the use of examples?

Since you are looking for a solution without $$\epsilon$$-transitions you can simply do this: create a NFA in which every original state $$q$$ two copies $$(q, 0)$$ and $$(q, 1)$$.

If a state was final then both its copies are final. If $$q_0$$ was the initial state, then $$(q_0, 0)$$ is the new initial state. Create the transition function as follows: if there was a transition $$q \to^a q'$$, then add the two new transitions $$(q, 0) \to^a (q', 1)$$ and $$(q, 1) \to^a (q', 0)$$.

It is easy to see that his NFA is equivalent to the initial one. You have essentially created a DFA which is a bipartite graph, and each transition changes the side of the bipartition the current state is in.

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.

• Empty transitions are not allowed in all definitions of NFA. There is a solution that does not introduce such $\varepsilon$-transitions. Actually, it works for deterministic automata too. Commented May 14, 2020 at 22:49

Say that a state $$q$$ has a self loop on symbol $$\alpha$$, create a new state $$q'$$ and remove the self loop from $$q$$.

Then

1. let $$q$$ and $$q'$$ have the same transitions,

2. if in $$q$$ on reading $$\alpha$$ go to $$q'$$, if in $$q'$$ on reading $$\alpha$$ go to $$q$$,

3. if $$q$$ is an accept state let $$q'$$ be also an accept state.

If we are in $$q$$ and we read $$\alpha$$ we go to $$q'$$, if we are in $$q'$$ and we read $$\alpha$$ we go to $$q$$ so point 2 replaces the self loop. If we are in $$q$$ or $$q'$$ and we read any symbol we go to the same state since both have the same transitions that is what point 1 does, and if $$q$$ is accepting then so is $$q'$$.

Formally :

For a state $$q$$ with a self loop on symbol $$\alpha$$:

Create a new state $$q'$$.

Remove $$\delta(q,\alpha) = q$$

Then for each transition $$\delta(q,\upsilon) = s$$, where $$s \in Q$$, and $$\upsilon\in\Sigma$$, add transition $$\delta(q'\upsilon) = s$$.

Add transitions $$\delta(q,\alpha) = q'$$ and $$\delta(q',\alpha) = q$$.

If $$q \in F$$, where $$F$$ is the set of accept states, then let $$q' \in F$$.