[2024][Febrero][Ejercicio 3][Parte a] Duda familia pumping lema

[2024][Febrero][Ejercicio 3][Parte a] Duda familia pumping lema

de Guillermo Coelho Morat -
Número de respuestas: 1

Hola, estuve trabajando en la parte a del ejercicio 3 donde se hace pumping lema para poder demostrar que el lenguaje no es regular. A la hora de resolverlo me enfrente a una duda en cuanto al largo de v para las diferentes familias ya que pueden haber tiras con p,q = 0. En la solución se trabaja con solo una familia la cual se le pone la restricción de que la cantidad de a's es mayor a 0. 

Como es el razonamiento aquí, por qué asume que la cantidad de a's en ese caso es mayor a 1, satisface la restricción del pumping lema pero no se estaría considerando el caso en que p = q = 0?



En respuesta a Guillermo Coelho Morat

Re: [2024][Febrero][Ejercicio 3][Parte a] Duda familia pumping lema

de Diego Garat -

hola:

no estaría entendiendo qué papel le estás asignando a p y q en tu zi.

cuando se aplica el contrarrecíproco del PL, se debe elegir una tira z en particular para la demostración (es la negación del "para todo z", de la formulación PL).  esa tira es tan particular como uno quiera, y se elige de forma de hacer posible (y facilitar al máximo) la descomposición. una vez elegida la tira z, las descomposiciones quedan establecidas porque son para _esa_ tira particular (y no cualquier otra). 

en tu ejemplo, la tira elegida  es a^N b^N c.  es una de las tantas que se podría haber elegido; por ejemplo, también valdría a^(N+1) b^(N+1) c.

la única descomposición u.v.w que cumple |uv| <=N debe necesariamente tener a u y v en las aes, pues son sus N primeros símbolos. 


saludos,

d.-