0
$\begingroup$

Let M = (Q, Σ, δ, q0, A) be an Ɛ-NFA and let S ⊆ Q

I am having problems starting this question. Would it be reasonable to find a proof for Ɛ(S) = S, and then proving Ɛ(S) = Ɛ(Ɛ(S))? If not, how would you go about doing this proof?

$\endgroup$
7
  • 3
    $\begingroup$ Could you please give the definition of Ɛ(S) ? $\endgroup$ – J.-E. Pin Oct 16 '19 at 4:17
  • $\begingroup$ Ɛ(S) is the same as eclosure(S), just saying we are taking the epsilon closure on the set S ⊆ Q $\endgroup$ – Ryan Gomez Oct 16 '19 at 16:22
  • $\begingroup$ Sorry to insist, but this is still not precise enough. Is Ɛ(S) the set of states $q$ such that there exists an Ɛ-path from some state of $S$ to $q$, or the the set of states $q$ such that there exists an Ɛ-path from $q$ to some state of $S$? By the way, giving a precise definition is an important step towards the answer to your question. $\endgroup$ – J.-E. Pin Oct 16 '19 at 16:31
  • 1
    $\begingroup$ No worries, it is the the set of states q such that there exists an Ɛ-path from q to some state of S $\endgroup$ – Ryan Gomez Oct 16 '19 at 16:42
  • $\begingroup$ How would you go about doing it with the other definition? Using the set of states q such that there exists an Ɛ-path from some state of S to q? I may have been confused on the definitions for the question. $\endgroup$ – Ryan Gomez Oct 16 '19 at 17:11
0
$\begingroup$

I would have taken the other definition, but let us work with your definition. First of all, $Ɛ(S)$ is not necessarily equal to $S$. Take for instance a two-state automaton containing only one Ɛ-transition, namely $$ 0 \xrightarrow{Ɛ} 1 $$ and let $S = \{1\}$. Then $Ɛ(S) = \{0, 1\}$ since there exists an $Ɛ$-path from $0$ to $1$ and also $Ɛ$-path from $1$ to $1$ (the empty path).

You should be able to prove that $Ɛ(Ɛ(S)) = Ɛ(S)$. Hint: the composition of two Ɛ-paths is an Ɛ-path.

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