[Ejercicio 1] [Parte 1] Pumping Lemma para LLC

[Ejercicio 1] [Parte 1] Pumping Lemma para LLC

de Nicolas Fabian Buero De La Fuente -
Número de respuestas: 10

Hola, buenas tardes. Estaba revisando el ejercicio 1.1 y me surgió la siguiente duda:

En el caso (vii) me queda:


¿Está bien lo de separar en casos según los valores de j y s? No encontré ningún "i" que me permita afirmar que Zi no pertenece al lenguaje para todos los casos. No sé si el error está desde la elección del z, ó si me estoy salteando algo.

Gracias, saludos.


En respuesta a Nicolas Fabian Buero De La Fuente

Re: Pumping Lemma para LLC

de Santiago Gongora -
Buenas tardes Nicolás,

aviso que no revisé toda la formulación del pumping, ni la familia en cuestión (porque tendría que corregir todo el ejercicio), por lo que voy a referirme solamente a la última imagen y responder tu pregunta.

La respuesta es que , está bien discutir en esos casos.  Fijate que lo que estás haciendo es agarrar una familia y subdividirla según los valores de j y s, lo cual está perfecto. Acordate que lo de agrupar en familias tiene una razón bien práctica: al agrupar, es posible hacer la demostración a mano de que todos los casos están contemplados.

Fijate que si existiera un superhéroe (el superPumping, ponele) que pudiera hacer la demostración para cada una de las posibles descomposiciones (una por una sin agrupar en familias) de la tira z no discutiría por casos ¿no? Iría una por una, descomposición a descomposición, y vería que se rompe. Pero, justamente, los humanos comunes y corrientes no podemos hacer eso :( y por esa razón es que tenemos que agrupar en familias de descomposiciones. Si a una de esas familias la subdividís, como hiciste, también está bien :D




Por último, en el caso j>0 \wedge s=0 ¿dice que i=\infty? Si es así, cuidado, que tenés que dar un i natural en concreto para romper el caso.
En respuesta a Santiago Gongora

Re: Pumping Lemma para LLC

de Nicolas Fabian Buero De La Fuente -
Muchas gracias por todo Santi! Quedó clarísimo. Lo del infinito fue bosquejando nomas jajaja, pido disculpas por la informalidad :)
En respuesta a Nicolas Fabian Buero De La Fuente

Re: Pumping Lemma para LLC

de Santiago Gongora -
Buenazo :) Me alegro que haya quedado claro.

Cualquier cosa preguntá.

Saludos,
Santi
En respuesta a Santiago Gongora

Re: Pumping Lemma para LLC

de Maria Agustina Simoncelli Maneiro -
Buenas! tengo una duda para este mismo tema. Al separar en casos, el i que encuentre para romper cada caso tiene que ser el mismo? gracias.
En respuesta a Maria Agustina Simoncelli Maneiro

Re: Pumping Lemma para LLC

de Santiago Gongora -

Hola Agustina,

Respuesta corta: No, no tiene por qué ser el mismo i para todos los subcasos.

Respuesta larga: Como le comentaba a Nicolás, lo que terminamos haciendo al discutir por casos es diferenciar familias dentro de la familia que estábamos analizando. Por lo tanto, al ser otras familias, se puede buscar un i para cada una de ellas, como es con todas las familias que se plantean al armar la tabla inicial. Podríamos pensarlo también "por absurdo": que se nos exigiera elegir un mismo i para cada subfamilia es como si exigiéramos elegir un mismo i para probar todos los casos de la tabla inicial (lo cual creo que está claro que no es así).

Acuérdense de eso, lo que significan las familias es

"agrupo un montón de descomposiciones z=uvwxy" parar probar que todas ellas "se rompen" de manera similar.

Si les queda más cómodo otro "agrupamiento de descomposiciones", entonces dividen de otra manera y muestran cómo se rompen. De lo que sí siempre se tienen que asegurar es que la demostración cubra todas las posibles descomposiciones  z=uvwxy.


Cualquier cosa vuelvan a consultar :)

Saludos,
Santi

En respuesta a Nicolas Fabian Buero De La Fuente

Re: Pumping Lemma para LLC

de Santiago Agustín Silveira Pérez -
Hola, respecto a este tema de estudiar los distintos casos me surgió una duda con una diapositiva de ejemplo. ¿Es necesario contemplar el caso q > 0 si ya encontré un i que me sirve para el caso q = 0?

Diapositiva
En respuesta a Santiago Agustín Silveira Pérez

Re: Pumping Lemma para LLC

de Juan Jose Prada -
Hola.
La respuesta a esta duda está justamente en este mismo hilo.
Uno cuando estudia las familias, trata de poner los casos (familias) genéricas, pero debe asegurarse de cubrir todos los casos (descomposiciones).
Cuando lo hacés para q=0 te faltan justamente todas aquellas descomposiciones - recordar que la aplicación es "para toda descomposición" - que son cuando q>0.
La distinción además es para mostrar que son casos (familias) diferentes a otras discutidas en otros de los análisis.
Saludos
Juanjo