Autor Tema: Probar Lema de Arden

0 Usuarios y 1 Visitante están viendo este tema.

29 Enero, 2018, 07:01 am
Leído 7641 veces

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Hola, como puedo probar el Lema de Arden considerando la ecuación entre lenguajes:

\( X = XM \cup N \) (1.2)
con \(  X  \) desconocida.


Partiendo que conozco lo siguiente:

\( X_0 = NM^* \) es solución de (1.2).

Si \( L \) es otra solución de la ecuación, entonces \( X_0  \subset{L} \)  Esto es, \( X_0 \) es la solución más pequeña de (1.2).

Si \( \epsilon \in{M} \) entonces para cualquier lenguaje \( S, X_S = (N \cup SM^*) \) es solución de (1.2).

Si \( \epsilon \in{M} \) entonces \( M^*M = M^* \).

Si \( \epsilon \not\in{M} \) entonces \( X_0 \) es la única solución de (1.2).

Sea \( L \) otra solución de (1.2), pruebe que para todo
\( n > 0, L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \);
 pruebe que si \( w \in L \) con \( \| w \|  = n  \) entonces \( w \) no puede estar en \( LM^{n+1} \) y por tanto tiene que estar en \(  \left(N \bigcup_{i=0}^nM^i\right) \)


Espero haberlo escrito correctamente, no pude corregir el error del límite, disculpa por eso, espero se entienda el enunciado.

Un saludo!!

29 Enero, 2018, 01:26 pm
Respuesta #1

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Edité tu mensaje para corregir los errores de \( \LaTeX \). Revisa que esté bien ahora.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

29 Enero, 2018, 11:08 pm
Respuesta #2

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Sí,  es correcto, gracias

30 Enero, 2018, 12:54 pm
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Sí,  es correcto, gracias

Sea \( L \) otra solución de (1.2), pruebe que para todo \( n > 0, L = LM^{n+1}\cup \left(N \cup \bigcup_{i=0}^nM^i\right) \); pruebe que si \( w \in L \) con \( \| w \|  = n  \) entonces \( w \) no puede estar en \( LM^{n+1} \) y por tanto tiene que estar en \( N \cup \bigcup_{i=0}^nM^i\subset NM^* \)

Revisa que esto sea realmente como lo tienes escrito. No es cierto que \( N \cup \bigcup_{i=0}^nM^i\subset NM^* \). Observa que sí es cierto que \( N\subset NM^* \) (ya que \( M^* \) incluye a la palabra vacía), pero es falso, en general, que \( \bigcup_{i=0}^nM^i\subset NM^* \). Si \( \epsilon\not\in N \), todas las palabras de \( NM^* \) tendrán como prefijo una de \( N \) y esto no se cumple para las de \( \bigcup_{i=0}^nM^i \).
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

30 Enero, 2018, 08:10 pm
Respuesta #4

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Tienes razón, está mal editado, lo correcto debería ser así:

\( n > 0, L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \)

Gracias por la observación, ya modifiqué el mensaje, así debería quedar.

Saludos.

31 Enero, 2018, 10:01 pm
Respuesta #5

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Quiero ver si estoy en lo correcto con lo siguiente:
Se cumple cuando \( X = NM \) , si la cadena vacía no está en \( n \).

Pero cuando entro a la fórmula empieza el problema, ya que no se ha de eliminar directamente...

verdad?

01 Febrero, 2018, 03:38 am
Respuesta #6

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Tienes razón, está mal editado, lo correcto debería ser así:

\( n > 0, L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \)

Ahora sí tiene sentido. Procede por inducción en \( n \).

Para \( n=1 \), por cumplirse (1.2), se tiene que \( L=LM\cup N \) luego

\( \begin{align*}
L=(LM\cup N)M\cup N&=LM^2\cup NM\cup N\\
&=LM^2\cup N(M\cup \{\epsilon\})\\
&=LM^2\cup N\big(\bigcup_{i=0}^1M^i\big)
\end{align*} \)

Ahora haz esencialmente lo mismo en el paso inductivo.

pruebe que si \( w \in L \) con \( \| w \|  = n  \) entonces \( w \) no puede estar en \( LM^{n+1} \) y por tanto tiene que estar en \(  \left(N \bigcup_{i=0}^nM^i\right) \)

Esta parte es inmediata. Si \( \epsilon \not\in M \), toda palabra de \( M \) tendrá largo mayor o igual o igual que 1, y por tanto toda palabra de \( M^{n+1} \) tendrá largo mayor o igual a \( n+1 \).
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

01 Febrero, 2018, 11:41 pm
Respuesta #7

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Gracias por la respuesta pero no estoy seguro de que por medio de inducción sea la forma de resolverlo, bueno, ciertamente tuve dificultades para realizar el paso inductivo pues viéndolo desde esta perspectiva:

En el paso 1)
sea \( y \in{ N M^*} \)\(  \Rightarrow{y = nm} \) donde \(  n \in{N} \) Y \( m \in{M^*} \)

Si \( y = n\epsilon \) \( \Rightarrow{y \in{N}} \) Y \( y \in{NM^* M\cup{N}} \)

Si \( y = nm \) con \( m  \neq{\epsilon}  \)\( \Rightarrow{y = n\in{m}} \) \( \in{NM^*M} \)\( \Rightarrow{y\in{NM^*M\cup{N}}} \)

2)

Si \( L = LM\cup{N} \) entonces \( NM^*\subset{L} \)

Si sabemos que \( NM^* = NM^* M\cup{N} = NM^*\cup{N} \)

Sea \( n\in{N}\Rightarrow{n\in{NM^*}} \) Y \( n\in{LM\cup{N}} = L \)


Bueno, no estoy muy seguro de lo que estoy haciendo pero creo esa es la manera de resolver los problemas, estoy en lo correcto?

Saludos.

02 Febrero, 2018, 01:46 am
Respuesta #8

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Bueno, no estoy muy seguro de lo que estoy haciendo pero creo esa es la manera de resolver los problemas, estoy en lo correcto?

Tú pareces querer demostrar el Lema de Arden directamente, o sea, si \( L \) satisface \( L=LM\cup N \) con \( \epsilon\not\in M \), entonces \( L=NM^* \). Pero dejas de lado lo que dice la letra:

Sea \( L \) otra solución de (1.2), pruebe que para todo
\( n > 0, L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \);
 pruebe que si \( w \in L \) con \( \| w \|  = n  \) entonces \( w \) no puede estar en \( LM^{n+1} \) y por tanto tiene que estar en \(  \left(N \bigcup_{i=0}^nM^i\right) \)

Mi sugerencia del mensaje anterior estaba destinada a probar lo que dice ahí, o sea que para todo \( n \), se cumple \( L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \). Lo que habría que preguntarse es: ¿para qué nos sirve este lema para probar el lema de Arden?


Spoiler
La prueba del Lema de Arden que ellos buscan creo que es ésta.

  • Primero que nada, \( NM^* \) es solución. Basta ver que \( (NM^*)M\cup N=NM^+\cup N\{\epsilon\}=N(M^+\cup \{\epsilon\})=NM^* \).

  • Luego se prueba que para todo \( n>0 \), \( L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \) (por inducción, como indiqué en mi mensaje anterior).

  • Por último, hay que ver que \( NM^* \) es la única solución. Para ello, consideremos una solución \( L \) arbitraria y probemos que \( L=NM^* \) por doble inclusión.
    • \( \fbox{$L\subset NM^*$} \)
      Tomemos una palabra \( w\in L \) y veamos que necesariamente esa palabra \( w \) está en \( NM^* \). Si \( w=\epsilon \), entonces como \( L=LM\cup N \) y \( \epsilon\not\in M \), tiene que cumplirse forzosamente que \( \epsilon\in N \), y en consecuencia \( \epsilon \in NM^* \). Si \( w\ne\epsilon \), entonces tiene un largo \( n>0 \). En virtud del ítem anterior, \( L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \). Como todas las palabras de  \( LM^{n+1} \) tienen largo mayor o igual a \( n+1 \), se tiene que \( w\in N \bigcup_{i=0}^nM^i\subset NM^* \).

    • \( \fbox{$NM^*\subset L$} \)
      \( L=LM\cup N\Rightarrow N\subset L\Rightarrow NM\subset LM\subset L\Rightarrow (NM)M\subset LM\subset L\Rightarrow \dots\Rightarrow NM^n\subset L,\forall n\ge 0 \).
      Como \( NM^i\subset L \) para todo \( i\ge 0 \), se sigue que \( \bigcup_i NM^i=N\bigcup_i M^i=NM^*\subset L \).
[cerrar]

Añado: La prueba "clásica" del lema de Arden es ésta. Pero imagino que si en este ejercicio les piden probar eso primero, será porque quieren que lo usen para la demostración del Lema de Arden.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

06 Febrero, 2018, 07:49 pm
Respuesta #9

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Bueno, no estoy muy seguro de lo que estoy haciendo pero creo esa es la manera de resolver los problemas, estoy en lo correcto?

Tú pareces querer demostrar el Lema de Arden directamente, o sea, si \( L \) satisface \( L=LM\cup N \) con \( \epsilon\not\in M \), entonces \( L=NM^* \). Pero dejas de lado lo que dice la letra:

Sea \( L \) otra solución de (1.2), pruebe que para todo
\( n > 0, L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \);
 pruebe que si \( w \in L \) con \( \| w \|  = n  \) entonces \( w \) no puede estar en \( LM^{n+1} \) y por tanto tiene que estar en \(  \left(N \bigcup_{i=0}^nM^i\right) \)

Mi sugerencia del mensaje anterior estaba destinada a probar lo que dice ahí, o sea que para todo \( n \), se cumple \( L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \). Lo que habría que preguntarse es: ¿para qué nos sirve este lema para probar el lema de Arden?


Spoiler
La prueba del Lema de Arden que ellos buscan creo que es ésta.

  • Primero que nada, \( NM^* \) es solución. Basta ver que \( (NM^*)M\cup N=NM^+\cup N\{\epsilon\}=N(M^+\cup \{\epsilon\})=NM^* \).

  • Luego se prueba que para todo \( n>0 \), \( L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \) (por inducción, como indiqué en mi mensaje anterior).

  • Por último, hay que ver que \( NM^* \) es la única solución. Para ello, consideremos una solución \( L \) arbitraria y probemos que \( L=NM^* \) por doble inclusión.
    • \( \fbox{$L\subset NM^*$} \)
      Tomemos una palabra \( w\in L \) y veamos que necesariamente esa palabra \( w \) está en \( NM^* \). Si \( w=\epsilon \), entonces como \( L=LM\cup N \) y \( \epsilon\not\in M \), tiene que cumplirse forzosamente que \( \epsilon\in N \), y en consecuencia \( \epsilon \in NM^* \). Si \( w\ne\epsilon \), entonces tiene un largo \( n>0 \). En virtud del ítem anterior, \( L = LM^{n+1}\cup \left(N \bigcup_{i=0}^nM^i\right) \). Como todas las palabras de  \( LM^{n+1} \) tienen largo mayor o igual a \( n+1 \), se tiene que \( w\in N \bigcup_{i=0}^nM^i\subset NM^* \).

    • \( \fbox{$NM^*\subset L$} \)
      \( L=LM\cup N\Rightarrow N\subset L\Rightarrow NM\subset LM\subset L\Rightarrow (NM)M\subset LM\subset L\Rightarrow \dots\Rightarrow NM^n\subset L,\forall n\ge 0 \).
      Como \( NM^i\subset L \) para todo \( i\ge 0 \), se sigue que \( \bigcup_i NM^i=N\bigcup_i M^i=NM^*\subset L \).
[cerrar]

Añado: La prueba "clásica" del lema de Arden es ésta. Pero imagino que si en este ejercicio les piden probar eso primero, será porque quieren que lo usen para la demostración del Lema de Arden.

Tienes razón, lo hacía de la manera equivocada.
Ya quedó,  me sirvió de mucha ayuda,  gracias !!