0
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ I don’t understand your reasoning. Try instead to use the definitions. $\endgroup$ Oct 18, 2019 at 22:56
  • $\begingroup$ I included a picture with an example hopefully it clarifies. $\endgroup$
    – Mandy
    Oct 18, 2019 at 23:11
  • $\begingroup$ A picture is not a proof. $\endgroup$ Oct 18, 2019 at 23:18
  • $\begingroup$ The sets $S,T$ could definitely have outgoing $\epsilon$-transitions. $\endgroup$ Oct 18, 2019 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$ Oct 19, 2019 at 8:04

1 Answer 1

2
$\begingroup$

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

$\endgroup$
0

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.