Suppose there are sets $S\subseteq Q, T\subseteq Q$ such that $T=\epsilon (T),S=\epsilon (S)$.

Prove $\epsilon(S\cap T)\subseteq S \cap T$

Definition of $\epsilon$- closure for epsilon NFA is:

$\epsilon : 2^Q \rightarrow 2^Q $

a) $S \subseteq \epsilon (S)$ Base case

b) If $q \in \epsilon (S)$ then $\delta(q,\epsilon )\subseteq \epsilon (S)$ Recursive case

c) and nothing else is in $\epsilon (S)$

And also, S is a set of all states in epsilon-NFA.

My proof:

Is this a correct reasoning?

Epsilon NFA example

  • $\begingroup$ I don’t understand your reasoning. Try instead to use the definitions. $\endgroup$ – Yuval Filmus Oct 18 '19 at 22:56
  • $\begingroup$ I included a picture with an example hopefully it clarifies. $\endgroup$ – Mandy Oct 18 '19 at 23:11
  • $\begingroup$ A picture is not a proof. $\endgroup$ – Yuval Filmus Oct 18 '19 at 23:18
  • $\begingroup$ The sets $S,T$ could definitely have outgoing $\epsilon$-transitions. $\endgroup$ – Yuval Filmus Oct 18 '19 at 23:19
  • 1
    $\begingroup$ As I explained in my answer to your previous question, you can't really prove anything using your "definition" of epsilon closure. $\endgroup$ – Yuval Filmus Oct 19 '19 at 8:04

Since your definition of $\epsilon$-closure isn't really a definition, it is impossible to prove anything using it. Instead, let me use the following definition: the $\epsilon$-closure of a set $S \subseteq Q$ consists of all states $x \in Q$ which are reachable from a state in $S$ by a (possibly empty) $\epsilon$-path (which is a path consisting of $\epsilon$-transitions).

Suppose that $\epsilon(S) = S$ and $\epsilon(T) = T$, and let $q \in \epsilon(S \cap T)$. Thus $q$ is reachable by a state $r \in S \cap T$ via an $\epsilon$-path. Since $r \in S \cap T$, in particular $r \in S$, and so, by definition, $q \in \epsilon(S) = S$. Similarly, $q \in \epsilon(T) = T$. Therefore $q \in S \cap T$.


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.