Buenas tenía una duda, no se puede demostrar que no es regular con una demostración similar a la de la parte b como la siguiente?
El lenguaje es: { #xy, x ∈ {0,1}*, y ∈ {0,1}*, |x|0 < |y|1 (cantidad de 0 de x < cantidad de 1 de y)}
Sería la misma idea pero tomando x=0^N e y=1^(N+1).
Sea N la constante del PL, y considere la tira z=#.0^N.1^(N+1), con x=0^N,y=1^(N+1)
Planteamos las descomposiciones de z en uvw que cumplen las dos primeras hipótesis del PL: |uv|≤ N y |v|>0.
Caso 1: u=ε ; v=#0^k ; w=0^(N-k).1^N+1 con k≥0- En ese caso z_2=#.0^k.#.0^k.0^(N-k).1^(N+1) no pertenece al lenguaje porque tiene dos símbolos
#
Caso 2: u=#0^k ; v=0^j ; w=0^(N-k-j) 1^(N+1) con k≥0, j>0
- En ese caso z_2=#0^k.0^(2j).0^(N-k-j).1^(N+1)=#0^(N+j).1^(N+1) que, como j>0, no pertenece al lenguaje
porque la cantidad de 0´s de x es al menos igual a la cantidad de 1´s de y.
Como esas son todas las descomposiciones posibles, y en cada caso encontré un i
para el que zi
no pertenece al lenguaje, por el contrarecíproco del PL, el lenguaje no
es regular.
Saludos