3
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ thank you, this proves in fact that it doesn't matter which idea we choose, both describe the same language. $\endgroup$
    – math boy
    Mar 23 at 14:30
4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$
    – math boy
    Mar 23 at 14:35

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.