Demostrar que la lengua $\{w \in \{a,b\}^* : \#w_b = \#w_a + 2 \}$ no es regular utilizando el lema del bombeo

Question

Tengo una pregunta. Tengo que probar que la lengua dada no es regular y no estoy seguro de estar haciéndolo correctamente.

La lengua es:

$ L = \{w \in \{a,b\}^* : \#w_b = \#w_a + 2 \}$

Así que usando el lema de bombeo demostraré que un lenguaje dado es regular. Tomo una cadena $ s =a^nb^nbb, s \in L$

Entonces, por el lema de bombeo $s = xyz$ Divido mi cadena en $x = a^n, y= b^n , z=bb $

Así que ahora puedo tomar la cuerda $ s = xyyz $ y vemos ahora que habrá más letras b en la palabra que a generada por la potencia por lo que la regla $ \#w_b = \#w_a + 2 $ está roto. Así que por el lema de bombeo el lenguaje dado no es regular.

Si pudierais comprobar si lo estoy haciendo correctamente, os lo agradecería mucho.

Answer 1

Más concretamente: dejemos que $N$ es el número de estados de una FSA que reconocen su idioma $L$ . Entonces, para cualquier palabra más larga que $N$ reconocido por su FSA, hay tres palabras $x$ , $y$ y $z$ tal que :

• $|y|\ge1$
• $|xy|\le N$
• para todos $n\in\mathbb N$ , $xy^nz\in L$ .

Ahora considere $a^Nb^{N+2}$ . Como es más grande que $N$ se puede resumir en tres palabras: $$a^Nb^{N+2}=xyz$$ Como usted tiene $|xy|\le N$ , $y=a^k$ para algunos $k\ge1$ . Pero entonces $$xyyz=a^{\alpha}a^{2k}a^{N-\alpha-k}n^{N+2}$$ no pertenece a su idioma $L$ porque $\#a+2=N+k+2\ne N+2=\#b-2$ .

Fin de la prueba.