[2012] [Segundo Parcial] [Ejercicio 2] Demostracion por Ogden.

[2012] [Segundo Parcial] [Ejercicio 2] Demostracion por Ogden.

de Federico Andres Aldunate Caramori -
Número de respuestas: 1

Solo quería saber si esta bien esta demostración por Ogden. Quiero demostrar que el lenguaje L2 = { w#w’#1 n , con w y w’ ∈ {0,1}*, con |w|=|w| y n = cantidad de símbolos diferentes en las mismas posiciones entre w y w’} no es un LIC.

Para tengo N constante de Ogden, Z=0N#1N#1N. Tomo como posiciones distinguidas los primeros N ceros.

Entonces tengo Z=uvwxy: Dist(vwx)<=N y Dist(vx)>=1. Entonces para cualquier combinación que cumpla eso, existe  Zi=uviwxiy, i>=0 tal que Zi no pertenece a L2, en particular i=0. Esto pasa por que con i=0, al menos un 0 desaparece(Dist(vx)>=1) y esto provoca que |w| =/= |w’|.

Quería saber si esta bien aplicado el Lema de Ogden, ya que me resulto más fácil, al menos para este caso particular.

En respuesta a Federico Andres Aldunate Caramori

Re: [2do Parcial 2012] Demostracion por Ogden.

de Diego Garat -

hola:

las condiciones sobre la descomposición en el lema de ogden se establecen sobre la cantidad de posiciones distinguidas pero no sobre el largo de las subtiras. esto hace que, por ejemplo, en tu demostración cumplan i y ii las descomposiciones de la forma:

u = 0N-j

v = 0j

w = 0k#1N#1m

x = 1p

y = 1N-p-m

y como esas descomposiciones, hay otras que deberías considerar... 

además, ni siquiera tu afirmación sería cierta: si v y x tiene el mismo largo,  v se forma con ceros de "w" y x con unos de "w'", en z0 se seguiría cumpliendo que los largos de lo que correspondería a w y w' son iguales.

saludos,

d.-