Rozdíl regulárních jazyků
Kapitoly: Uzavřenost regulárních jazyků, Sjednocení, Průnik, Rozdíl, Doplněk, Zřetězení, Uzávěr
Mějme dva regulární jazyky L1, L2. Dokážeme, že jejich rozdíl L = L1 ∖ L2 je také regulární jazyk.
Idea
Ve skutečnosti není moc co dokazovat. Pro rozdíl dvou množin totiž platí následující vztah:
$$ L_1 \setminus L_2 = L_1 \cap L_2^\prime, $$
kde $L_2^\prime$ je doplněk jazyka L2. Z kapitol o průniku regulárních jazyků a doplňku regulárních víme, že regulární jazyky jsou na obě tyto operace uzavřené. To znamená, že dokážeme sestrojit automat, který přijímá průnik jazyků a doplněk jazyku. Tyto automaty tak můžeme použít k sestrojení automatu, který bude přijímat jazyk $L_1 \cap L_2^\prime$, což je ale zároveň jazyk L1 ∖ L2.
Příklad
Mějme tento automat A1, který přijímá všechna slova, která obsahují sudý počet 1:
a automat A2, který příjmá slova obsahující lichý počet 0:
Sestrojíme automat, který bude přijímat rozdíl těchto jazyků. Potřebujeme tak automat $A_2^\prime$, který bude doplňkem k automatu A2. Jen prohodíme koncové a nekoncové stavy:
Teď už jen sestrojíme automat A, který bude přijímat průnik jazyků L(A1) a $L(A_2^\prime)$:
