Tenemos dos idiomas: . Sabemos que es un lenguaje regular, por lo que mi pregunta es si es regular.
Trato de encontrar una manera de demostrarlo ...
No puedo suponer, por supuesto, que son regulares ...
Así que busco una forma de demostrarlo.
Me gustaría obtener alguna pista!
¡Gracias!
Respuestas:
No,L2L1 no es necesariamente regular.
Deje , que es regular, y , que no lo es. Entonces es el conjunto de todas las cadenas que terminan en , que es regular, pero es el conjunto de todas las cadenas que comienzan con , comienzan con un número distinto de cero de s seguido de al menos s. Este lenguaje no es regular, ya que su intersección con es , que no es -regular.L1={0,1}∗ L2={1}∪{0n1n∣n≥1} L1L2 1 L2L1 1 0 1 {0m1n∣m,n≥1} {0m1n∣1≤m≤n}
fuente
Estaba publicando solo una pista, luego vi otras respuestas completas, así que esta es una solución completa (oculta) sucinta :-)
fuente
Esto no es una pista, sino una respuesta completa. No sigas leyendo si todavía estás tratando de resolverlo.
No hay necesidad deL2⋅L1 ser regular
DejarUNA ser un lenguaje unario (no regular) tal que A ⋅ A es regular Tales idiomas se pueden encontrar en la publicación aquí . AsumirUNA está sobre el alfabeto { a } .
DefinirL1= { b } ⋅ A y L2= A ⋅ { b } . Entonces, obtienesL1⋅L2= { b } ⋅UNA2⋅ { b } , que es regular. Sin embargo,L2⋅L1=A⋅{bb}⋅A , que puede demostrarse fácilmente que no es regular, según A ser no regular
fuente
Las siguientes reglas definen el lenguaje asociado con cualquier expresión regular. Regla 1 El idioma asociado con la expresión regular que es solo una letra es esa palabra de una letra sola y el idioma asociado con A es solo {A}, un idioma de una palabra. Regla 2 Si r, es una expresión regular asociada con el lenguaje L, y r 2 es una expresión regular asociada con el lenguaje L2, entonces,
(i) La expresión regular (rl) (r2) está asociada con el lenguaje L, multiplicado por L 2. idioma (r, r2) = L1L 2 (ii) La expresión regular r, + r2 está asociada con el lenguaje formado por unión de los conjuntos L1 y L2. language (rl + r2) = L, + L2 (iii) El lenguaje asociado con la expresión regular (rl) * es LI *, el cierre de Kleene del conjunto LI como un conjunto de palabras. idioma (rl *) = L1 *
fuente