Säännöllisten kielten erotus

Olkoon meillä kaksi säännöllistä kieltä L₁, L₂. Todistamme, että niiden erotus L = L₁ ∖ L₂ on myös säännöllinen kieli.

Idea

Itse asiassa ei ole juuri mitään todistettavaa. Kahden joukon erotukselle pätee nimittäin seuraava yhtälö:

$$L_1\setminus L_2=L_1\cap L_2^c,$$

jossa $L_2^c$ on kielen L₂ komplementti. Säännöllisten kielten leikkauksesta ja säännöllisen kielen komplementista kertovista luvuista tiedämme, että säännölliset kielet ovat suljettuja kummankin operaation suhteen. Se tarkoittaa, että voimme rakentaa automaatin, joka hyväksyy kielten leikkauksen, ja automaatin, joka hyväksyy kielen komplementin. Näitä automaatteja voimme siis käyttää sellaisen automaatin rakentamiseen, joka hyväksyy kielen $L_1\cap L_2^c$, joka on samalla kieli L₁ ∖ L₂.

Esimerkki

Olkoon meillä tämä automaatti A₁, joka hyväksyy kaikki sanat, joissa on parillinen määrä ykkösiä:

ja automaatti A₂, joka hyväksyy sanat, joissa on pariton määrä nollia:

Rakennamme automaatin, joka hyväksyy näiden kielten erotuksen. Tarvitsemme siis automaatin A₂′, joka on automaatin A₂ komplementti. Vaihdamme vain lopputilat ja ei-hyväksyvät tilat keskenään:

Nyt enää rakennamme automaatin A, joka hyväksyy kielten L(A₁) ja L(A₂′) leikkauksen:

Lähteet

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