Przecięcie i połączenie języka regularnego i nieregularnego

Niech będzie regularne, regularne, nie regularne. Pokaż, że nie jest regularne lub podaj kontrprzykład. $L_1$ $L_1 \cap L_2$ $L_2$ $L_1 \cup L_2$

Próbowałem tego: spójrz na . Ten jest regularny. Mogę w tym celu zbudować automat skończony: jest regularny, jest regularny, więc usuń wszystkie ścieżki (ilość skończona) dla ze skończonej liczby ścieżek dla . Pozostało więc skończonych ścieżek do tego wszystkiego. Ta rzecz różni się od , ale jak mogę udowodnić, że związek $L_1 \setminus (L_2 \cap L_1)$ $L_1$ $L_2 \cap L_1$ $L_1 \cap L_2$ $L_1$ $L_2$ (zwykły) i (nieregularny) nie jest regularny? $L_1 \setminus (L_1 \cap L_2)$ $L_2$

formal-languages regular-languages

— Kevin
źródło

„więc usuń wszystkie ścieżki (ilość skończona) dla

ze skończonej liczby ścieżek dla

” - co to ma znaczyć? Zwykłym sposobem skonstruowania automatu dla różnicy jest użycie

i dobrze znanych konstrukcji dla uzupełnienia i przecięcia.

L_{1} \cap L_{2}

$L_1\cap L_2$

L_{1}

$L_1$

A ∖ B = A \cap \bar{B}

$A \setminus B = A \cap \overline{B}$

— Raphael

Wolę zmienić tytuł tego pytania. Sam tytuł pytania jest błędnym stwierdzeniem.

— nitishch,

Odpowiedzi:

Możemy to udowodnić przez sprzeczność. Pozwala zdefiniować . Następnie możemy przeformułować : $\overline{L_1} = \Sigma^* \setminus L_1$ $L_2$

$L_2 = ((L_1 \cup L_2) \setminus L_1) \cup (L_1 \cap L_2) = ((L_1 \cup L_2) \cap \overline{L_1}) \cup (L_1 \cap L_2)$

Wiemy:

Zwykłe języki są zamknięte w ramach unii, skrzyżowania i uzupełnienia
$\overline{L_1}$ $L_1 \cap L_2$
$L_2$

$L_1 \cup L_2$ $((L_1 \cup L_2) \cap \overline{L_1}) \cup (L_1 \cap L_2)$ $L_2$ $L_1 \cup L_2$

— Mike B.
źródło

Myślę, że rozumiem. Ale dlaczego uzupełnienie zwykłego języka jest regularne? Nie rozumiem tej części.

— Kevin

@Kevin Jest to dobrze znany lemat, więc powinieneś znaleźć dowód w dowolnym podręczniku. Jedną z metod dowodowych jest wzięcie automatu skończonego i zamiana stanów akceptujących i nieakceptujących: otrzymujesz automat rozpoznający język dopełniacza.

— Gilles 'SO - przestań być zły'

A = {a, b}

$A = \{a,b\}$

a

$a$

L (M) = {a}

$L(M)=\{a\}$

{a}

$\{a\}$

Dowód Gillesa działa tylko w przypadku deterministycznych automatów skończonych, co - dla zwykłych języków - nie jest ograniczeniem. Ale jak powiedział, ten lemat można znaleźć w dowolnym podręczniku.

— Mike B.

@Kevin: Mike oznacza, że każdy zwykły język ma deterministyczny automat do rozpoznania go, więc zawsze możesz go używać.

— reinierpost

-4

$L_1 = \{a, b\}^*$ $L_2 = \{a^n b^n : n \ge 0\}$ $L_1$ $L_2$ $L_1 \cup L_2 = L_1$

— vonbrand
źródło

Nie udało Ci się spełnić warunku, że

jest regularny.

L_{1} \cap L_{2}

$L_1 \cap L_2$

— Andrej Bauer,