Si es un lenguaje normal, entonces es regular para?

8

Tenemos dos idiomas: . Sabemos que es un lenguaje regular, por lo que mi pregunta es si es regular.L1,L2L1L2L2L1

Trato de encontrar una manera de demostrarlo ...

No puedo suponer, por supuesto, que son regulares ... Así que busco una forma de demostrarlo. L1,L2

Me gustaría obtener alguna pista!

¡Gracias!

stud1
fuente
Continuemos esta discusión en el chat .
Raphael

Respuestas:

7

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}{0n1nn1}L1L21L2L1101{0m1nm,n1}{0m1n1mn}

David Richerby
fuente
Gracias David, pero ¿por qué está el " " en ? ¿Por qué lo necesitamos? ¡Gracias! {1}L2
stud1
1
@ stud1 Para garantizar que sea ​​regular. L1L2
David Richerby
Pero (sin el ) sigue siendo todas las palabras que terminan con , ¿verdad? Entonces, todavía trato de entender por qué necesitamos el , espero que esté bien, lo pregunto :-) ¡Gracias! L1L2{1}1{1}
stud1
1
@ stud1 Si elimina entonces, por ejemplo, . En términos más generales, las únicas cadenas que estarían en serían las que terminan en para . {1}1L1L2L1L20mwnmn1
David Richerby
1
@ stud1 Correcto.
David Richerby
13

Estaba publicando solo una pista, luego vi otras respuestas completas, así que esta es una solución completa (oculta) sucinta :-)

Dejar L1={1pp is prime}, L2={10}; tenemosL1L2={11+0} que es regular, pero L2L1={101pp is prime} que no es regular

Vor
fuente
1
Solución elegante!
Anton Trunov
2
@AntonTrunov: bastante elegante :-) L2={10} se puede usar para "enmascarar" cualquier UNARY no regular L1, pero tan pronto como se cambian L1está "expuesto" de nuevo :-)
Vor
¿Cuál es el significado de + a 11+?
stud1
1
@ stud1: 1+ significa "uno o más 1s"; en otras palabras, es un" atajo "para {1nn1}. Entonces{11+0}={110,1110,11110,...}
Vor
6

Esto no es una pista, sino una respuesta completa. No sigas leyendo si todavía estás tratando de resolverlo.

No hay necesidad de L2L1 ser regular

Dejar UNA ser un lenguaje unario (no regular) tal que UNAUNAes regular Tales idiomas se pueden encontrar en la publicación aquí . AsumirUNA está sobre el alfabeto {una}.

Definir L1={si}UNA y L2=UNA{si}. Entonces, obtienesL1L2={si}UNA2{si}, que es regular. Sin embargo,L2L1=A{bb}A, que puede demostrarse fácilmente que no es regular, según A ser no regular

Shaull
fuente
1

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 *

Shashi Kumar
fuente