lema de bombeo $a^{n} (b a^{n-1})n$ tiempos donde $n$ disminuye cada vez que

Question

Hola estoy atascado tratando de demostrar que el siguiente lenguaje $K = \{a, a^2ba, a^3ba^2ba,...\}$ no es un lenguaje regular. En realidad, simplemente no puedo encontrar una palabra w que tenga una longitud de al menos p y esté en el lenguaje $K$ .

Gracias.

Answer 1

Tenga en cuenta que, para cada palabra en este idioma, si la palabra comienza con $n$ $a$ s, seguido de un $b$ entonces la palabra tiene una longitud $$\underbrace{\frac{1}{2}n(n + 1)}_{\text{The number of $ a $s}} + \underbrace{n - 1}_{\text{The number of $ b $s}}.$$ Además, el número de líderes $a$ s también determina de forma única la palabra; en cuanto vemos $a^n b \ldots$ , entonces conocemos el resto de la palabra.

Ahora, supongamos que una palabra $w \in K$ tenía una subcadena bombeable $y$ es decir, existen subcadenas $x, y, z$ tal que $w = xyz$ , $y \neq \varepsilon$ y $xy^nz \in K$ para todos $n \ge 0$ .

Ahora, si $xy$ consiste únicamente en $a$ s, entonces $xy^nz$ contendrá un número diferente de encabezamientos $a$ s como $n$ varía. Sin embargo, el número de $b$ s seguirá siendo el mismo, lo que contradice la fórmula anterior. Por lo tanto, $xy$ debe contener al menos un $b$ .

Si $x$ contiene un $b$ , entonces todo el segmento de la conducción $a$ s se produce en $x$ y, por tanto, no cambia con $n$ . Dado que el número de líderes $a$ s determina de forma única la palabra, debemos tener $xyz = xy^nz$ para todos $n$ que se contradice con $y \neq \varepsilon$ .

Por lo demás, $x$ sólo contiene $a$ s, pero $y$ contiene al menos un $b$ . Tenga en cuenta que $xy^nz$ , para $n \ge 1$ , todavía comienza con $xy$ que sigue conteniendo el mismo número de $a$ s seguido de un $b$ . Como tal, de nuevo tenemos que tener $xyz = xy^nz$ una contradicción.