Rozdíl regulárních jazyků

Mějme dva regulární jazyky L₁, L₂. Dokážeme, že jejich rozdíl L = L₁ ∖ L₂ 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₂′ je doplněk jazyka L₂. Z kapitol o průniku regulárních jazyků a doplňku regulárního jazyka 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 jazyka. Tyto automaty tak můžeme použít k sestrojení automatu, který bude přijímat jazyk L₁ ∩ L₂′, což je ale zároveň jazyk L₁ ∖ L₂.

Příklad

Mějme tento automat A₁, který přijímá všechna slova, která obsahují sudý počet 1:

a automat A₂, který přijímá 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₂′, který bude doplňkem k automatu A₂. Jen prohodíme koncové a nekoncové stavy:

Teď už jen sestrojíme automat A, který bude přijímat průnik jazyků L(A₁) a L(A₂′):

Zdroje

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools