Sea regular, L 1 ∩ L 2 regular, L 2 no regular. Demuestre que L 1 ∪ L 2 no es regular o dé un contraejemplo.
Intenté esto: Mira . Este es regular. Puedo construir un autómata finito para esto: L 1 es regular, L 2 ∩ L 1 es regular, así que elimine todos los caminos (cantidad finita) para L 1 ∩ L 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 ∖ ( L (regular) y L 2 (no regular) no es regular?
Respuestas:
Sabemos:
fuente
fuente