1
$\begingroup$

Suppose I have an NFA with accepting state q1(which is also an accept state) and non-accept state q2, with ε-transition from q1 to q2.

Also, suppose that empty string is inside the language. Then I want to know if the empty string is accepted by the above NFA following the standard definition:

Here, $\mathcal{P}(Q)$ denotes the power set of Q. Let $w = a_1 a_2 \ldots a_m$ be a word over the alphabet $\Sigma_\epsilon$. The automaton $M$ accepts the word $w$ if a sequence of states, $r_0,r_1, \ldots, r_n$ exists in $Q$ with the following conditions with $m >= n$ and $m>=0$:

$r_0 = q_0$

$r_i+1 \in \Delta(r_i, a_i+1)$, for $i = 0, \ldots, n−1$

$r_n \in F$

I know it would be much easier to figure out whether the given string is accepted by NFA by visualizing what's going on in the NFA, but I find the formal definition above rather confusing because it's only checking the existence of one particular branch of computation that satisfies the above three conditions. I know that an empty string is w = ε or [blank]. By blank, I mean it has no symbols (where m = 0). But if I take w = ε, it would move from q1 to q2 via following ε-transition.But if I take w = [blank], then the sequence of state would be just q0, then it would be accepted. Is this the right way of thinking about it?

$\endgroup$
  • $\begingroup$ $\epsilon$-transitions are never obligatory. $\endgroup$ – Yuval Filmus Nov 1 '17 at 12:34
  • $\begingroup$ "I have an NFA with accepting state q1(which is also an accept state)", do you mean it is also the starting state? Otherwise this statement seems redundant. $\endgroup$ – mikeazo Nov 1 '17 at 12:48
  • $\begingroup$ Sorry it's a typo "I have an NFA with initial state q1(which is also an accept state)" $\endgroup$ – Ted Nov 1 '17 at 17:06
  • $\begingroup$ So you couldn't have edited it two months ago? Bah. $\endgroup$ – Rick Decker Jan 31 '18 at 1:12
  • $\begingroup$ It's because I didn't have enough reputation. $\endgroup$ – Ted Jan 31 '18 at 16:58
1
$\begingroup$

Is this the right way of thinking about it?

No.

An NFA (with or without $\varepsilon$-transitions) accepts if there is any sequence of transitions that leads to an accepting state, regardless of whether there are other sequences that lead to non-accepting states. If the start state is accepting, then the empty string is accepted because the null sequence of transitions (no transitions at all) leads to an accepting state. It doesn't matter that there are other sequences that lead to non-accepting states.

$\varepsilon$-transitions are annoying to define formally. Informally (but completely accurately), they just allow the automaton to change state without reading an input character.

$\endgroup$
0
$\begingroup$

Perhaps the following alternative description of NFA with $\epsilon$-transitions would help clarify matters. The first step is to replace $\epsilon$ with some other symbol, say $\underline{\epsilon}$, in the NFA. We can now think of it as an NFA without $\epsilon$ transitions. The semantics of the NFA are as follows:

For an alphabet $\Sigma$, let $h\colon \Sigma \cup \{\underline{\epsilon}\} \to \Sigma^*$ denote the homomorphism which deletes $\underline{\epsilon}$: $h(\sigma) = \sigma$ for $\sigma \in \Sigma$, and $h(\underline{\epsilon}) = \epsilon$.

An NFA with $\underline{\epsilon}$-transitions over $\Sigma$ accepts a word $w$ if and only if it accepts some word in $h^{-1}(w)$ *as an NFA over $\Sigma \cup \{\underline\epsilon\}$.

In words, suppose that $A$ is a NFA with $\underline\epsilon$ transitions over an alphabet $\Sigma$. We can also consider it as an NFA $A'$ over $\Sigma \cup \{\underline\epsilon\}$ without $\underline\epsilon$ transitions. The automaton $A$ accepts a word $w$ iff $A'$ accepts some word $w'$ such that if we delete all $\underline\epsilon$ symbols from $w'$ then we obtain $w$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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