[dayan]

Hola buen día!
Se pide comprobar que \[ ECLOSURE(q)  \] o para abreviar \[ Cl(q)  \]

a) Mostrar que en general \[ Cl(S \cap{T}) \not= Cl(S) \cap{Cl(T) } \] ¿Cúal siempre es subconjunto del otro?
Mi intuición me dice que \[ Cl(S \cap{T}) \subseteq{}Cl(S) \cap{Cl(T) } \] pues notemos que  \[ S\cap{T} \] puede ser vacía, y como el vacío elemento de todo conjunto se sigue que \[ \emptyset \in Cl(S) \cap{Cl(T)}  \]
Pero no hallo la forma de demostra lo formalmente

b) Mostrar que en general \[ Cl(\bar{S}) \not= \overline{Cl(S)} \] ¿Cúal siempre es subconjunto del otro?
En este por más ejemplos que intento no me sale que alguna sea subconjunto del otro

Alguien una idea?
Gracias!

[martiniano]

Hola.

Para el primero ten en cuenta que como \( S\cap{T}\subseteq{S} \) es \[ (S\cap{T})^*\subseteq{S^*} \]. Por razones idénticas \[ (S\cap{T})^*\subseteq{T^*} \]. Entonces ya \[ (S\cap{T})^*\subseteq{S^*}\cap{T^*} \].

Como ejemplo de que la igualdad no se cumple toma \[ S=\{a,b\} \] y \[ T=\{ab\} \].

Para el segundo, simplemente:

\[ w\in{\overline{S^*}}\;\Rightarrow{\;}w\not\in{S^*}\;\Rightarrow{\;}w\not\in{S}\;\Rightarrow{\;}w\in{\overline{S}}\;\Rightarrow{\;}w\in{}\left(\overline{S}\right)^* \].

Como ejemplo de que no se cumple la igualdad te sirve cualquier lenguaje que no coincida con su clausura.

Un saludo.

PD. Disculpa. No me he dado cuenta y he utilizado \[ S^* \] para referirme a la clausura de Kleene de \[ S \]. Supongo que era a lo que te referías tú con \[ ECLOSURE \], ¿verdad?

[dayan]

Hola.

Para el primero ten en cuenta que como \( S\cap{T}\subseteq{S} \) es \[ (S\cap{T})^*\subseteq{S^*} \]. Por razones idénticas \[ (S\cap{T})^*\subseteq{T^*} \]. Entonces ya \[ (S\cap{T})^*\subseteq{S^*}\cap{T^*} \].

Como ejemplo de que la igualdad no se cumple toma \[ S=\{a,b\} \] y \[ T=\{ab\} \].

Para el segundo, simplemente:

\[ w\in{\overline{S^*}}\;\Rightarrow{\;}w\not\in{S^*}\;\Rightarrow{\;}w\not\in{S}\;\Rightarrow{\;}w\in{\overline{S}}\;\Rightarrow{\;}w\in{}\left(\overline{S}\right)^* \].

Como ejemplo de que no se cumple la igualdad te sirve cualquier lenguaje que no coincida con su clausura.

Un saludo.

PD. Disculpa. No me he dado cuenta y he utilizado \[ S^* \] para referirme a la clausura de Kleene de \[ S \]. Supongo que era a lo que te referías tú con \[ ECLOSURE \], ¿verdad?

Gracias!
Aunque no me refería a \[ ECLOSURE  \] como la cerradura de kleene. Quizá me faltó especificar que que para \[ AFN-\epsilon \] donde \[ ECLOSURE \] es la cerradura de epsilon.
No sé si las propiedades se apliquen igual

[martiniano]

Hola.

Pues entonces, ¿te importa poner cómo te han definido a la clausura-\[ \epsilon \]? ¿Y lo que son \[ S \] y \[ T \]? Me cuesta encajar la pregunta en lo que tengo yo sobre la clausura-\[ \epsilon \].

Un saludo.

[dayan]

Hola.

Pues entonces, ¿te importa poner cómo te han definido a la clausura-\[ \epsilon \]? ¿Y lo que son \[ S \] y \[ T \]? Me cuesta encajar la pregunta en lo que tengo yo sobre la clausura-\[ \epsilon \].

Un saludo.

Claro!
Definición de \[ ECLOSURE \]. Sea \[ q \in Q \] la cerradura de \[ \epsilon \] de \[ q \] denotada como \[ ECLOSURE(q)  \] es el estado de todos los estados alcanzables desde \[ q \] usando cualquier secuencia de transiciones \[ \epsilon \]. Esto incluye a la secuencia de longitud 0.

Sea \[ S\subseteq{Q} \] la cerradura \[ \epsilon \] del conjunto \[ S \] se define como \[ ECLOSURE(S) = \bigcup_{r \in ECLOSURE(S) } ECLOSURE (r)  \]

Ahora \[ ECLOSURE(q)  \] se puede encontrar de manera inductiva con los pasos siguientes: (se le conoce como la versión del tiempo)

Caso base
\[ ECLOSURE_0(q):={q} \]

Inducción
\[ ECLOSURE_{t+1}:=ECLOSUREt(q) _ \cup{} \{ r \in \delta(p, \epsilon) | p \in ECLOSURE_t(q), r \not\in ECLOSURE_t(q) \}  \]

Termina cuando
\[ ECLOSURE_{t+1}(q) = ECLOSURE_t(q)  \]

[martiniano]

Hola.

Pues si lo he entendido bien funciona todo salvo el contraejemplo que te di para el primer apartado. En lugar de eso considera el siguiente conjunto de estados con sus transiciones épsilon:



Y toma \[ S=\{A\}  \] y \[ T=\{B\}  \]

Un saludo.