0
$\begingroup$

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?

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented May 14, 2020 at 22:49
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.