En el ejercicio se pide que se clasifique el siguiente lenguaje segun la jerarquia de Chomsky, L2 = { x#xP#xI / x= a1a2a3...a2n-1a2n ; xP = a2a4....a2n ;
xI = a1a3....a2n-1 ai є {a,b} }. Entonces para probar que el mismo no es libre de contexto se utiliza el CR de PL.
La tira que se toma es z = a^2N#a^N#a^N. al hacer todas las descomposiciones de la tira, en la familia 4 que es la siguiente:
u=a^2N-p-q
v=a^p
w=a^q#a^r
x=a^s
y=a^N-r-s#a^N
con |vx| = p+s >= 1 y |vwq| = p+q+1+r+s <=N
se discute segun zi = a^2N-p-q (a^p )^i a^q#a^r (a^s )^ i a^Nr-s#a^N, en los casos en que p es distinto de 0 con s=0 y el caso en que p=0 y s distinto de 0. Sin embargo, no se toma en cuenta el caso en que tanto s como p sean distintos de 0. Tomando en cuenta ese caso no logro darme cuenta de que i seleccionar de forma de que la tira no pertenezca al lenguaje. ¿Acaso no hay que tomar en cuenta ese caso?, desde ya muchas gracias.