TeoLeng: [2014] [Segundo Parcial] [Ejercicio 2] [Parte a] Ogden

buenas tardes,

intenté resolver este ejercicio por contrarrecíproco de Ogden , tomando z = a^n0^nb^n1^n , y como posiciones distinguidas 0^n ..

Para todas las familias que me quedaron (5) pude encontrar un i tal que Zi no pertenece al lenguaje.

Mi duda es respecto al uso de Ogden.

1) Tomar 0^n como posiciones distinguidas está bien? Aparentemente llegué a probar que no es LC, pero mi elección de las posiciones distinguidas fue al azar.

2) Existe alguna "estrategia" para darse cuenta cuales posiciones conviene tomar como distinguidas...

Y en general:

3) Como me doy cuenta si tengo que usar PL o Ogden? existe alguna "estrategia"?

4) Y principalmente, como me doy cuenta que no puedo probar por PL?

Gracias.

Re: [Ejercicio 2a 2014] /Ogden

de Diego Garat - martes, 26 de junio de 2018, 15:52

hola:

antes que nada, nunca se plantea en una evaluación de esta asignatura a un lenguaje en el que sólo sea posible aplicar ogden para su resolución sin avisarles. en cambio sí se puede pedir _explicitamente_ que apliquen ogden en lugar del PL en un lenguaje cualquiera.

en general, ogden te puede servir en algunos casos para simplificar la demostración o para resolver algunos lenguajes que no salen por el PL, pero no son los que por lo general se ven en este curso. como casi cualquier demostración, no existe "una forma" de darse cuenta cuáles son las mejores posiciones distinguidas, va un poco en el lenguaje y en la pericia de cada uno.

respecto al lenguaje particular que planteaste, según tu elección de tira, y asumiendo que n es la constante de ogden, lo que sucede es que cualquier descomposición uvwxy que tenga al menos un 0 en vx es válida, dado que no hay restricciones en los largos y sí en las cantidades de posiciones distinguidas.

así, la siguiente descomposición válida, ¿cómo la probaste?

u=a^n0^n-1

v= 0

w = b^n

x= 1

y = 1^n-1

saludos,

d.-