hola:
sí, tu tira serviría y tendría sólo una descomposición. un detalle menor, elegiría z=aN+1bN+2a para asegurar que p>0.
saludos,
d.-
Ah es verdad no me había dado cuenta de ese detalle, gracias!
Buenas tardes.
Dado que t puede ser igual a 0, no puedo elegir la tira z= aNbN ?
Habiendo leído en el foro que cuantos más cambios de símbolos hay en la tira z, mayor cantidad de familias (https://eva.fing.edu.uy/mod/forum/discuss.php?d=100572#p246452), lo primero que hago es ver si puedo eliminar alguno de los símbolos de la tira.
Agradezco desde ya la respuesta, saludos.
Me sumo a la duda!
Buenas tardes,
por lo que tengo entendido, z= aNbN , sería una tira apta para probar el pumping, dado que se cumplen las tres cosas importantes: pertenece al lenguaje, su longitud es mayor a N y no es computable con un AFD (o generable mediante una E.R.).
Gracias por adelantado
hola:
un detalle: esta afirmación no es correcta: "pertenece al lenguaje, su longitud es mayor a N y no es computable con un AFD (o generable mediante una E.R.)." lo que no se podría generar, denotar o reconocer, en todo caso, es un lenguaje con esa forma, no la tira en sí. una tira w siempre es reconocida por algún AFD; basta considerar al lenguaje regular {w}.
sobre la pregunta: efectivamente, la tira elegida serviría para el PL, aunque no agrega ni quita familias respecto a, por ejemplo,
z= aN+1 bN+2 a
para el primer PL solo los N primeros símbolos son los que determinan la cantidad de familias, basta tomarlos iguales (si es posible) para que todas las descomposiciones (que cumplen i y ii) se puedan expresar con una única familia.
lo que NO es recomendable para este lenguaje es elegir a z=a bN+1 aN, que tiene dos familias debido a la letra a del comienzo.
un último detalle: la letra indica p>0, con lo que, para ser más prolijos en la demostración, lo mejor sería tomar
z= aN+1 bN+1
saludos,
d.-
Gracias por responder, Diego.
¿Cómo sería la forma correcta de describir esa "condición" que expresé de forma errónea?
Uno de mis errores durante el curso fue tomar una tira Z que no probaba el pumping y la razón era esa (quería demostrar que no era libre de contexto pero tomaba una tira que pertenecia a un lenguaje libre de contexto) y cuando Juanjo me lo explicó, lo entendí. Pero ¿Cómo sería la manera correcta de expresarlo?
Gracias de antemano
hola:
la afirmación es una especie de "regla a ojo" que te permite aproximar si un lenguaje es o no de cierto tipo, y digo esto porque a veces, si está mal planteada, la regla no funciona bien.
básicamente lo que se dice es que la tira "no tiene forma de lenguaje libre de contexto" (PL2) o "de lenguaje regular" (PL1). ¿qué es que una tira no tiene "forma" de cierto lenguaje? es una idea intuitiva; por ejemplo, la tira z=a^N b^N del caso anterior no tiene forma regular porque las cantidades son las mismas, lo que me lleva ---variando el N--- a un lenguaje que ya sé que no es regular. si tomase z=a^N b^M ahora sí tiene "forma de regular", porque las cantidades no están relacionadas.
lo que estamos diciendo en realidad es que, dada la tira z=a^N b^N, el lenguaje {a^N b^N / N nat} no es regular, por lo que esa tira en ppio me serviría para este PL. la idea que hay detrás es que si una tira tuviese "forma regular" ---o sea, el lenguaje Lr asociado es regular---, si saliese el CPL con esa tira en el lenguaje de la demostración, probablemente podría probar que el propio Lr no es regular tomando esa misma tira, lo que es absurdo.
como ya mencioné, esto no es formal, sino más bien una regla práctica para orientarse en la demostración.
saludos,
d.-
Ah, genial, ahora sí. Me parecía importante entender bien qué era lo que estaba afirmando.
Gracias de nuevo.