Intersección y unión de un lenguaje regular y otro no regular.

12

Sea regular, L 1L 2 regular, L 2 no regular. Demuestre que L 1L 2 no es regular o dé un contraejemplo.L1L1L2L2L1L2

Intenté esto: Mira . Este es regular. Puedo construir un autómata finito para esto: L 1 es regular, L 2L 1 es regular, así que elimine todos los caminos (cantidad finita) para L 1L 2 de la cantidad finita de caminos para L 1 . Así que hay una cantidad finita de caminos para todo esto. Esta cosa es disjunta de L 2 , pero ¿cómo puedo probar que la unión de L 1( LL1(L2L1)L1L2L1L1L2L1L2 (regular) y L 2 (no regular) no es regular?L1(L1L2)L2

Kevin
fuente
"así que elimine todos los caminos (cantidad finita) para de la cantidad finita de caminos para L 1 " - ¿qué se supone que significa eso? La forma habitual de construir un autómata para la diferencia es mediante el uso de A B = A ¯ B y las construcciones bien conocidas para el complemento y la intersección. L1L2L1AB=AB¯
Raphael
Prefiero cambiar el título de esta pregunta. Por sí mismo, el título de la pregunta es una afirmación incorrecta.
nitishch

Respuestas:

19

L1¯=ΣL1L2

L2=((L1L2)L1)(L1L2)=((L1L2)L1¯)(L1L2)

Sabemos:

  • Los idiomas regulares están cerrados bajo unión, intersección y complemento
  • L1¯L1L2
  • L2

L1L2((L1L2)L1¯)(L1L2)L2L1L2

Mike B.
fuente
Creo que lo tengo. Pero, ¿por qué el complemento de un lenguaje regular es regular? No entiendo esa parte.
Kevin
1
@Kevin Este es un lema bien conocido, por lo que debe encontrar una prueba en cualquier libro de texto. Un método de prueba es tomar un autómata finito e intercambiar los estados de aceptación y no aceptación: se obtiene un autómata que reconoce el idioma del complemento.
Gilles 'SO- deja de ser malvado'
A={a,b}aL(M)={a}{a}
La prueba de Gilles funciona solo para autómatas finitos deterministas, que, para los idiomas normales, no es una restricción. Pero como él dijo, este lema se puede encontrar en cualquier libro de texto.
Mike B.
1
@Kevin: Mike significa que cada lenguaje regular tiene un autómata determinista para reconocerlo, por lo que siempre puedes usar uno.
reinierpost
-4

L1={a,b}L2={anbn:n0}L1L2L1L2=L1

vonbrand
fuente
55
No ha cumplido la condición de que es regular. L1L2
Andrej Bauer el