Tengo dos preguntas:
Considero que el siguiente idioma En otras palabras, no es palíndromo con una longitud uniforme. Probé que este lenguaje NO es regular al demostrar que su complemento no es regular. Mi pregunta es cómo probarlo usando el lema de bombeo sin usar el complemento.
Deje que Probé que este lenguaje no es regular usando clases de equivalencia. ¿Cómo puedo probarlo usando el lema de bombeo?
Muchas gracias por editar :)
Respuestas:
No todos los idiomas no regulares fallan en la prueba del lema de bombeo. Wikipedia tiene un ejemplo molestamente complejo de un lenguaje no regular que puede ser bombeado. Entonces, incluso si un idioma no es regular, es posible que no podamos probar este hecho utilizando el lema de bombeo.
Pero resulta que podemos usar el lema de bombeo para demostrar que su primer idioma no es regular. No estoy seguro sobre el segundo.
Reclamo: no es regular.L1
Prueba: por el lema de bombeo. Sea la longitud de bombeo. (Voy a usar el alfabeto lugar de .) Si , entonces tome la cadena , que está en y bombee a que no está en , entonces no sería regular.p {a,b} {0,1} p=1 abbaa L1 aabbaa L1 L1
Sip>1 , luego toma la cuerda apbbaN . (Averiguaremos lo que queremosN para ser más tarde.) Luego considere cualquier división de la cadena en xyz dónde x=ap−k , y=ak y z=bbaN .
Ahora vamos a bombear esta cuerdai veces. (Averiguaremos lo que queremosi para ser más tarde.) Obtenemos la cuerda xyiz , lo que da ap−kaikbbaN=ap−k+ikbbaN .
Ahora retrocedamos. Primero elegimosN . Entonces, alguna elección dek se hizo. Entonces, elegimosi . Queremos descubrir quéN elegir para que, para cualquier elección de k∈[1,p] , podemos elegir un i eso hace que esta cuerda sea un palíndromo al hacer el número de a s a la izquierda es igual al número a la derecha. (Siempre tendrá una longitud uniforme).
Así que siempre queremos conseguir esop−k+ik=N . Si jugamos con las matemáticas, descubrimos que debemos elegirN=p+p! y recoger i=p!/k+1 .
Para recapitular, elegimosN=p+p! y elegí la cuerda apbbaN . Entonces alguna elección dek fue hecho para que la cuerda estuviera compuesta de unap - kyb bunanorte dónde y=unak . Luego escogimosi = p ! / k + 1 . Bombeamos la cuerda para obtenerunap - kyyob bunanorte=unap - kunayo kb bunanorte=unap - k + i kb bunanorte .
Pero sabemos quep−k+ik=p−k+(p!k+1)k=p−k+p!+k=p+p! . YN=p+p! . Entonces el número dea s en ambos extremos es el mismo, por lo que la cadena es un palíndromo de longitud uniforme, por lo que no está en L1 , entonces L1 No es regular. □
fuente
Para la pregunta uno, la cadena0p12p0p+p! es un contraejemplo adecuado. Cualquiera que sea la longitud dey es decir, debe ser un factor de p! , así que lo bombeamos lo suficiente y obtenemos p+p! ceros al inicio.
fuente
Después de pensarlo mucho, creo que respondí 2.
elegimos string (010) ^ N (101) ^ N, donde N es la longitud de bombeo. No importa qué y elegiremos, xy ^ 0z tendrá más 101 que 010. La idea es que solo podemos agregar más 101 subcadenas en la primera parte de la cadena o eliminar algunas subcadenas 010.
fuente