Interesante prueba de idiomas formales.

Question

Encontré este ejercicio (9.14) en el capítulo 9 del libro "Lógica Dinámica" de Harel, Kozen y Tiuryn. No tengo absolutamente ninguna pista de cómo proporcionar una prueba para el ejercicio.

Demuestra que para cualquier idioma $L$ sobre el alfabeto $\{a\}$ y cualquier lenguaje regular infinito $ \alpha $ sobre el alfabeto $\{a\}$ el lenguaje de la concatenación $L \alpha $ es regular.

Especialmente lo que pasa cuando $L$ es el lenguaje de todas las palabras del alfabeto $\{a\}$ que las longitudes son de números primos.

Answer 1

Esto no es, por desgracia, cierto. Toma $L = \{a^p \mid \text {$ p $ is an odd prime} \}$ y dejar $K = 1 + a(a^2)^*$ . El lenguaje $K$ es infinito y regular. Además, como $L$ es un subconjunto de $a(a^2)^*$ uno obtiene $$ La(a^2)^* \subseteq a(a^2)^*a(a^2)^* \subseteq (a^2)^*. $$ Supongamos que $LK$ es regular. Entonces $LK \cap a(a^2)^*$ también sería regular. Pero $$ LK = L(1 + a(a^2)^*) = L + La(a^2)^* $$ y por lo tanto $LK \cap a(a^2)^* = L$ que no es regular. Contradicción.