Pruebas usando el lema de bombeo regular

8

Tengo dos preguntas:

  1. 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.

    L1={w{0,1}u{0,1}:w=uuR}.
    w
  2. Deje que Probé que este lenguaje no es regular usando clases de equivalencia. ¿Cómo puedo probarlo usando el lema de bombeo?

    L2={w{0,1}w has same number of 101 substrings and 010 substrings}.

Muchas gracias por editar :)

vidente
fuente
Nota. Mi navegador no muestra el signo "no existe" en la descripción de . No se preocupe: está allí en la fuente, y el cambio de navegadores ayudó. L1
Hendrik Jan

Respuestas:

7

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=1abbaaL1aabbaaL1L1

Si p>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=apk, y=aky z=bbaN.

Ahora vamos a bombear esta cuerda iveces. (Averiguaremos lo que queremosi para ser más tarde.) Obtenemos la cuerda xyiz, lo que da apkaikbbaN=apk+ikbbaN.

Ahora retrocedamos. Primero elegimosN. Entonces, alguna elección dekse 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 as a la izquierda es igual al número a la derecha. (Siempre tendrá una longitud uniforme).

Así que siempre queremos conseguir eso pk+ik=N. Si jugamos con las matemáticas, descubrimos que debemos elegirN=p+p! y recoger i=p!/k+1.

Para recapitular, elegimos N=p+p! y elegí la cuerda apbbaN. Entonces alguna elección dek fue hecho para que la cuerda estuviera compuesta de unapags-kysisiunanorte dónde y=unak. Luego escogimosyo=pags!/ /k+1. Bombeamos la cuerda para obtenerunapags-kyyosisiunanorte=unapags-kunayoksisiunanorte=unapags-k+yoksisiunanorte.

Pero sabemos que pk+ik=pk+(p!k+1)k=pk+p!+k=p+p!. YN=p+p!. Entonces el número deas 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.

usul
fuente
¡Respuesta perfecta!
vidente
Muchas gracias por la ayuda La idea quiere elegir una cuerda sabiamente.
vidente
Me hubiera gustado darte una respuesta a ambos idiomas, ¡pero el segundo parece doloroso! El enfoque que me llevó a la respuesta sobre la primera fue tratar de demostrar queL1en realidad es bombeable: cuando llegué al caso final y no pude probarlo, pude comenzar a ver cómo construir la cadena de arriba.
usul
@usul, ¿cómo llegaste a esto? N=p+p!, i=p!/k+1i=p!/k+1?
Dima Knivets
3

Para la pregunta uno, la cadena 0p12p0p+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.

Luke Mathieson
fuente
1

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.

vidente
fuente
Desafortunadamente no parece funcionar :( La cadena 010010101101 (N = 2) tiene tres (!) Ocurrencias de cada una. Al eliminar la tercera letra, obtenemos 01010101101, que todavía tiene tres ocurrencias de 010. Cuidado con la superposición. Todavía estoy perplejo. ...
Hendrik Jan
¡Si! ¡Pero tenemos 4 ocurrencias de 101! ¡Y así cantidad de 101
subcadenas
Ups Lo siento. Debería haber leído lo que dijiste exactamente: "agrega más 101 subcadenas". +1 (caso cerrado)
Hendrik Jan