Lema de bombeo y $L \subset \{a\}^*$

Question

Dejemos que $L \subset \{a\}^*$ y $L$ satisface el lema de la bomba. Demostrar que $L$ es regular.

Por favor, ayúdame.

Mi un intento:

Definición . Una lengua $L$ de $A^∗$ es reconocido por un monoide $M$ si existe un morfismo monoide11 $f:A^* \rightarrow M$ y un subconjunto $X$ de $M$ tal que $f^{-1}(X)=L$ .

Datos . Un lenguaje es regular si y sólo si es reconocido por algún monoide finito. Sea $A = \{a\}$ Bien, dejemos $M = (\mathbb{N}, +, 0) $ sea un monoide. Y dejemos que $h : A^* \rightarrow M$ sea un homomorfismo definido: $h(s) = |s|$ . Ahora, deberíamos encontrar tal $X$ que $h^{-1}[X] = L$ . Por lo tanto, consideremos $h[L]$ . h[L] es un conjunto con un número que significa la longitud de las palabras en $L$ . Por lo tanto, dejemos $X = h[L] $ . Es importante observar que $h$ es la inyección $A = \{a\}$ .

Esta prueba no se utiliza para el lema de bombeo. Tengo que demostrar que el lema de bombeo es necesario y suficiente aquí. Por lo tanto, pido ayuda para encontrar dicha prueba, así como para comprobar mi prueba.

Answer 1

Primero definamos una notación útil: decimos que un número entero positivo $w \in \mathbb{Z}$ pertenece a L si $a^w \in L$ . En otras palabras, $w \in L \iff a^w \in L$ .

Demostraremos que un lenguaje que satisface el lema de bombeo es periódico a partir de algún punto. En otras palabras, existen números $s, f \in \mathbb{N}$ y un conjunto de residuos $F \subset [0..f)$ modulo $f$ tal que para cada $w \ge s$ tenemos $w \in L \iff w \mod f \in F$ . Estas lenguas son claramente regulares.

El lema de bombeo afirma que existe $p \ge 1$ de manera que cada $w \in L$ con $w \ge p$ puede escribirse como $w = x + y + z$ con las siguientes condiciones:

1. $y \ge 1$
2. $x + y \le p$
3. para todos $i \ge 0: x+iy+z \in L$

Podemos repetirlo:

$$ w + i \cdot y \in L, y \le p $$

En otras palabras, a partir de $w$ cada número que es congruente con $w$ modulo $y$ pertenece a $L$ . Eso ya es algo periódico. Sabemos que por cada $w \in L$ existe el correspondiente $y_w \le p$ tal que $w + i \cdot y_w \in L$ . Tomemos el mínimo común múltiplo de todos ellos $y_w$ . Dado que todos ellos son menores que $p$ sólo hay un número finito de distintos $y_w$ y por lo tanto su lcm está bien definido. Denotémosla $f$ . Es el periodo que buscamos. De hecho, sabemos que si $w \in L$ entonces $w + f \in L$ (ya que $f$ es un múltiplo de $y_w$ por construcción). Ahora en cada clase residual módulo f podemos tomar el primer número que pertenece a $L$ (si hay al menos uno). Definamos $s$ como el máximo de todos esos números. Entonces está claro que $w + f \in L$ y $w \ge s$ entonces $w \in L$ . Eso es lo que necesitamos: partir de $s$ el conjunto de números $w \in L$ es periódica con periodo $f$ .