Cómo puede un lenguaje formal $L$ concatenado con sí mismo $L^k$siempre igual $L^{k+1}$

Question

Estoy en busca de una explicación de cómo un lenguaje formal L concatenado con el mismo $k$ veces $L^k$, igual que con el mismo idioma concatenado con el mismo $k+1$ veces $L^{k+1}$.

El problema en el que estoy trabajando específicamente me pide para proporcionar algunos de lenguaje $L$ $Σ={a}$ tal que $L^3 = L^4$, pero $L \neq L^2$$L^2 \neq L^3$. Intuitivamente, esto no tiene sentido para mí. Aparentemente $L^{k+1}$ siempre debe ser mayor en la cardinalidad de a $L^k$, y por lo tanto ser desigual. Supongo que la respuesta se relaciona con la cadena nula siendo en $L$, pero no estoy seguro de cómo o por qué.

Podría alguien aclarar que mi intuición me lleva por mal camino? Gracias por la información.

Answer 1

Tome por ejemplo, $L=\{\varepsilon,a,aaaa,aaaaa,aaaaaa,\ldots\}$.

Answer 2

Claramente, si la palabra más corta en $L$ tiene longitud $n$, la palabra más corta en $L^k$ tiene longitud $kn$. Así que si $\epsilon\notin L$ y $L^k\ne L^{k+1}$ $kn\ne (k+1)n$. Por otro lado, si el null string $\epsilon$ es en $L$ entonces el $L^k\subseteq L^{k+1}$, pero no necesariamente $L^k= L^{k+1}$ % (que no quieres para $k=1$ y $k=2$ de todos modos).

Suponga que tenemos un lenguaje $L_0$ tal que $L_0^2=L_0$ y una palabra $\alpha$ tal que $\alpha,\alpha^2,\alpha^3\notin L_0$, $\alpha^4\in L_0$. $L=L_0\cup\{\alpha\}$ Hace el trabajo (¿por qué?). Ahora observe que usted puede escoger por ejemplo $L_0=(aaaa)^*=\{\,a^{4n}\mid n\in\mathbb N_0\,\}$ y $\alpha=a$.