Differanse av regulære språk
La oss ha to regulære språk L1, L2. Vi skal bevise at differansen L = L1 ∖ L2 også er et regulært språk.
Ideen
Egentlig er det ikke mye å bevise. For differansen av to mengder gjelder nemlig denne sammenhengen:
der L2′ er komplementet til språket L2. Fra kapitlene om snittet av regulære språk og komplementet til et regulært språk vet vi at regulære språk er lukket under begge disse operasjonene. Det betyr at vi kan konstruere en automat som aksepterer snittet av språk og komplementet til et språk. Disse automatene kan vi derfor bruke til å konstruere en automat som skal akseptere språket L1 ∩ L2′, og det er samtidig språket L1 ∖ L2.
Eksempel
La oss ha denne automaten A1, som aksepterer alle ord som inneholder et like antall enere:
og automaten A2, som aksepterer ord som inneholder et odde antall nuller:
Vi konstruerer en automat som skal akseptere differansen av disse språkene. Vi trenger altså en automat A2′ som er komplementet til automaten A2. Vi bytter bare om sluttilstandene og tilstandene som ikke er sluttilstander:
Nå konstruerer vi bare automaten A, som skal akseptere snittet av språkene L(A1) og L(A2′):
Kilder
Kapitler: Lukkethet av regulære språk, Union av regulære språk, Snitt av regulære språk, Differanse av regulære språk, Komplementet til et regulært språk, Konkatenering av regulære språk, Kleene-stjernen til et regulært språk
