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

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?

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