# in NFA is every state itself contained in set generated by transition function when considering epsilon transition from that state?

in $$\epsilon$$-NFA (NFAs involving $$\epsilon$$ transitions) when we have $$\epsilon$$ transitions, I understand it as where can we go if we don't read any symbol from the input tape, then I think every state $$q$$ from which we are considering transition must belong to $$\delta(q,\epsilon)$$ because if we don't read anything, we can of course stay in the state where we are at now, I am asking whether $$\epsilon$$ transition from state to itself is assumed? for example, if we have some state $$q_i$$ which has $$\epsilon$$ transition to state $$q_j$$ then is $$\delta(q_i, \epsilon)$$=$$\{q_j, q_i\}$$ or just $$\{q_j\}$$, I think it's just matter of convention and wouldn't make significant difference.

Why not make this a bit formal and let's do the following exercise:
For a given NFA, $$M = (Q, \Sigma, \delta, q_0, F)$$, let us construct another NFA $$M' = (Q, \Sigma, \delta', q_0, F)$$ where $$\delta'$$ is the same as $$\delta$$ with additional $$\epsilon$$-transition self-loop on every state. We would like to prove these two machines are equivalent, that is, $$L(M) = L(M')$$.

Proof for $$L(M) \subseteq L(M')$$:
For every string $$w \in L(M) \subseteq \Sigma^*$$, there is a transition path in $$M$$ from $$q_0$$ to some final state $$q \in F$$. By construction the same path also exist in $$M'$$ thus $$w \in L(M')$$.

Proof for $$L(M') \subseteq L(M)$$:
For every string $$w \in L(M') \subseteq \Sigma^*$$, there is a transition path in $$M'$$ from $$q_0$$ to some final state $$q \in F$$. Now, due to our additional $$\epsilon$$-transition self-loops, this path may contain runs (consecutive repetitions) of the same states. Now if we collapse each run into just a single state, it will give us a trace on $$M$$ from $$q_0$$ to the same final state $$q \in F$$. Thus, $$w \in L(M)$$.

• thank you, this proves in fact that it doesn't matter which idea we choose, both describe the same language. Commented Mar 23 at 14:30

The answer depends on what you mean by $$\delta(q,\epsilon)$$.

First possibility is that $$\delta$$ specifies the transitions (the arrows in the state diagram). In that case we have $$\delta(q_i,\epsilon) =\{q_j\}$$ to indicate the single edge.

The other possibility is that $$\delta$$ specifies computations, sometimes called the extended transition function: $$q\in \delta(p,w)$$ iff there is a computation on the input word $$w$$ starting in state $$p$$ and ending in state $$q$$. In that case $$\delta(q_i,\epsilon) =\{q_i,q_j\}$$ is what we need.

• thank you for the answer. computation vs transition perspective is interesting, fact that both idea describe the same language is shown in the answer above, so I accept the above answer, however this idea is interesting as well. so I upvote it as well, thank you! Commented Mar 23 at 14:35