Me he encontrado con esa pregunta: "Dé ejemplos de dos idiomas regulares en los que su unión no genere un idioma regular".
Esto es bastante impactante para mí porque creo que los idiomas regulares están cerrados bajo unión. Lo que significa para mí que si tomo dos idiomas regulares y los combino, debo obtener un idioma regular.
Y creo que entiendo la prueba de eso: en mis palabras, si los idiomas son regulares, entonces existen autómatas que los reconocen. Si tomamos todos los estados (unión), y agregamos un nuevo estado para el punto de entrada, y modificamos la función de transición para el nuevo estado con epsilon, estamos bien. También mostramos que existe un camino desde cada estado, etc.
¿Me puede decir dónde estoy equivocado, o tal vez otra forma de abordar la pregunta.
Fuente de la pregunta, ejercicio 4, en francés.
Además, se hace la misma pregunta con la intersección.
Respuestas:
Hay una diferencia significativa entre la pregunta a medida que la plantea y la pregunta planteada en el ejercicio. La pregunta pide un ejemplo de un conjunto de idiomas regulares modo que su unión no sea regular. Tenga en cuenta el rango de la unión: a . Los lenguajes regulares están cerrados bajo unión finita , y las pruebas se ejecutan a lo largo de las líneas que bosquejas en la pregunta, sin embargo, esto se desmorona bajo unión infinita . Podemos mostrar esto tomando para cada (conL = ∞ ⋃ i = 1 L i 1 ∞ L i = { 0 i 1 i } i Σ = { 0 , 1 } L = { 0 i 1 i ∣ i ∈ N }L1,L2,…
Como comentario aparte, podemos ver fácilmente dónde falla la prueba normal. Imagine la misma construcción en la que agregamos un nuevo estado inicial y -transitions a los antiguos estados iniciales. Si hacemos esto con un conjunto infinito de autómatas, hemos construido un autómata con un número infinito de estados, lo que obviamente contradice la definición de autómata finito .ε
Por último, supongo que la confusión puede surgir de la formulación de la pregunta original, que comienza con "Donner deux exemples des suites de langages ...", que es (¡
aproximadamente, mi francés está un poco oxidado, pero verificado externamente!) "Dé dos ejemplos de secuencias de idiomas ...", en lugar de "Dé dos ejemplos de idiomas ...". Sin embargo, una lectura incauta puede confundir el segundo con el primero.fuente
Para su segunda pregunta, considere los idiomas definidos por Observe que para cualquier , es regular, ya que (1) el conjunto izquierdo es finito y, por lo tanto, regular, (2) el conjunto derecho se denota por la expresión regular así que es regular, y (3) los idiomas regulares están cerrados bajo uniones finitas, como ya sabe.
No es demasiado difícil demostrar que para cualquier número entero tenemos y, por lo tanto, así que inductivamente tenemos (que en realidad no necesitamos aquí, pero es demasiado bonito para dejarlo de lado).n≥1 Mn+1⊆Mn Mn∩Mn+1=Mn+1
Ahora observe que no contiene , por lo que ninguna de estas cadenas estará en la intersección completa. Como consecuencia tendremos que se sabe que no es un lenguaje normal. (Si no conocía este hecho, está en muchos textos teóricos y la prueba bien vale la pena leerla).a n 2 + 1 , aMn an2+1,an2+2,…,a(n+1)2−1
fuente
¿Por qué elegir lenguajes regulares complicados para mostrar que los conjuntos regulares no están cerrados bajo una unión infinita? Los lenguajes singleton son suficientes para mostrar que cualquier lenguaje RE es una unión infinita de conjuntos regulares.
Tome cualquier lenguaje recursivamente numerable . Cada cadena tiene un índice de enumeración . Deje . Cada es un conjunto singleton, por lo tanto, regular. Pero es RE.L w∈L i=index(w) Li={w∣i=index(w)} Li L=⋃∞i=1Li
Del mismo modo, al definir , tenemos los conjuntos que son regulares como complementos de un conjunto singleton. Entonces que es el complemento de , por lo tanto, co-RE. Y eso se puede lograr con cualquier conjunto de co-RE.Mi=Σ∗∖Li Mi ⋂∞i=1Mi=Σ∗∖L L
Por lo tanto, cualquier lenguaje recursivo es una unión infinita de conjuntos regulares, y también una intersección infinita de conjuntos regulares (no los mismos, sino sus complementos :).
El infinito está lleno de sorpresas, y lo que es cierto para valores arbitrariamente grandes puede no ser cierto en el infinito.
fuente
Si hace la Unión de infinitos conjuntos de unidades, puede hacer cualquier idioma (bueno, al menos, cualquier idioma, porque si no se puede decidir, no puede especificar la lista de todas sus cadenas). Por ejemplo, la unión de conjuntos de unidades donde cada uno contiene una cadena de palíndromo diferente sobre {a, b}, da como resultado el lenguaje de palíndromo (sin contexto): esto es{ϵ}⋃{a}⋃{b}⋃{aa}⋃{bb}⋃{aaa}⋃{aba}⋃{bab}⋃{bbb}⋃ ...
Puede hacer algo similar con la intersección, haciendo infinitos conjuntos donde cada uno es , donde es la ésima palabra del palíndromo, resultando el lenguaje de todas las palabras no palíndromas (complemento del lenguaje palíndromo, no -regular).Σ∗−{pi} pi i
fuente