23/10/2018, 05:43:43 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Puedes practicar LATEX con el cómodo editor de Latex online
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Probar Lema de Arden  (Leído 941 veces)
0 Usuarios y 2 Visitantes están viendo este tema.
Antoniio
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
México México

Mensajes: 258


Ver Perfil
« : 29/01/2018, 03:01:40 am »

Hola, como puedo probar el Lema de Arden considerando la ecuación entre lenguajes:

[texx]X = XM \cup N[/texx] (1.2)
con [texx] X [/texx] desconocida.


Partiendo que conozco lo siguiente:

[texx]X_0 = NM^*[/texx] es solución de (1.2).

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

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

Si [texx]\epsilon \in{M}[/texx] entonces [texx]M^*M = M^*[/texx].

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

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


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

Un saludo!!
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.311


Ver Perfil
« Respuesta #1 : 29/01/2018, 09:26:38 am »

Edité tu mensaje para corregir los errores de [texx]\LaTeX[/texx]. Revisa que esté bien ahora.
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
Antoniio
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
México México

Mensajes: 258


Ver Perfil
« Respuesta #2 : 29/01/2018, 07:08:13 pm »

Sí,  es correcto, gracias
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.311


Ver Perfil
« Respuesta #3 : 30/01/2018, 08:54:16 am »

Sí,  es correcto, gracias

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

Revisa que esto sea realmente como lo tienes escrito. No es cierto que [texx]N \cup \bigcup_{i=0}^nM^i\subset NM^*[/texx]. Observa que sí es cierto que [texx]N\subset NM^*[/texx] (ya que [texx]M^*[/texx] incluye a la palabra vacía), pero es falso, en general, que [texx]\bigcup_{i=0}^nM^i\subset NM^*[/texx]. Si [texx]\epsilon\not\in N[/texx], todas las palabras de [texx]NM^*[/texx] tendrán como prefijo una de [texx]N[/texx] y esto no se cumple para las de [texx]\bigcup_{i=0}^nM^i[/texx].
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
Antoniio
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
México México

Mensajes: 258


Ver Perfil
« Respuesta #4 : 30/01/2018, 04:10:29 pm »

Tienes razón, está mal editado, lo correcto debería ser así:

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

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

Saludos.
En línea
Antoniio
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
México México

Mensajes: 258


Ver Perfil
« Respuesta #5 : 31/01/2018, 06:01:09 pm »

Quiero ver si estoy en lo correcto con lo siguiente:
Se cumple cuando [texx]X = NM[/texx] , si la cadena vacía no está en [texx]n[/texx].

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

verdad?
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.311


Ver Perfil
« Respuesta #6 : 31/01/2018, 11:38:20 pm »

Tienes razón, está mal editado, lo correcto debería ser así:

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

Ahora sí tiene sentido. Procede por inducción en [texx]n[/texx].

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

[texx]\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*}[/texx]

Ahora haz esencialmente lo mismo en el paso inductivo.

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

Esta parte es inmediata. Si [texx]\epsilon \not\in M[/texx], toda palabra de [texx]M[/texx] tendrá largo mayor o igual o igual que 1, y por tanto toda palabra de [texx]M^{n+1}[/texx] tendrá largo mayor o igual a [texx]n+1[/texx].
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
Antoniio
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
México México

Mensajes: 258


Ver Perfil
« Respuesta #7 : 01/02/2018, 07:41:07 pm »

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 [texx]y \in{ N M^*}[/texx][texx] \Rightarrow{y = nm}[/texx] donde [texx] n \in{N}[/texx] Y [texx]m \in{M^*}[/texx]

Si [texx]y = n\epsilon[/texx] [texx]\Rightarrow{y \in{N}}[/texx] Y [texx]y \in{NM^* M\cup{N}}[/texx]

Si [texx]y = nm[/texx] con [texx]m  \neq{\epsilon} [/texx][texx]\Rightarrow{y = n\in{m}}[/texx] [texx]\in{NM^*M}[/texx][texx]\Rightarrow{y\in{NM^*M\cup{N}}}[/texx]

2)

Si [texx]L = LM\cup{N}[/texx] entonces [texx]NM^*\subset{L}[/texx]

Si sabemos que [texx]NM^* = NM^* M\cup{N} = NM^*\cup{N}[/texx]

Sea [texx]n\in{N}\Rightarrow{n\in{NM^*}}[/texx] Y [texx]n\in{LM\cup{N}} = L[/texx]


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.
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.311


Ver Perfil
« Respuesta #8 : 01/02/2018, 09:46:36 pm »

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 [texx]L[/texx] satisface [texx]L=LM\cup N[/texx] con [texx]\epsilon\not\in M[/texx], entonces [texx]L=NM^*[/texx]. Pero dejas de lado lo que dice la letra:

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

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


Spoiler (click para mostrar u ocultar)

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.
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
Antoniio
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
México México

Mensajes: 258


Ver Perfil
« Respuesta #9 : 06/02/2018, 03:49:57 pm »

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 [texx]L[/texx] satisface [texx]L=LM\cup N[/texx] con [texx]\epsilon\not\in M[/texx], entonces [texx]L=NM^*[/texx]. Pero dejas de lado lo que dice la letra:

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

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


Spoiler (click para mostrar u ocultar)

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 !!
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!