Differens av reguljära språk

Låt L₁, L₂ vara två reguljära språk. Vi bevisar att deras differens L = L₁ ∖ L₂ också är ett reguljärt språk.

Idén

Egentligen finns det inte mycket att bevisa. För differensen av två mängder gäller nämligen följande samband:

$$L_1\setminus L_2=L_1\cap L_2^{\prime },$$

där L₂′ är komplementet till språket L₂. Av avsnitten om snitt av reguljära språk och om komplementet till ett reguljärt språk vet vi att reguljära språk är slutna under båda de här operationerna. Det betyder att vi kan konstruera en automat som accepterar snittet av språk och en automat som accepterar komplementet till ett språk. Dem kan vi använda för att konstruera en automat som accepterar språket L₁ ∩ L₂′, som ju också är språket L₁ ∖ L₂.

Exempel

Låt oss ta den här automaten A₁, som accepterar alla ord som innehåller ett jämnt antal ettor:

och automaten A₂, som accepterar ord som innehåller ett udda antal nollor:

Vi konstruerar en automat som accepterar differensen av de här språken. Då behöver vi en automat A₂′ som är komplementet till automaten A₂. Vi byter bara plats på sluttillstånden och de icke-accepterande tillstånden:

Nu konstruerar vi bara automaten A som accepterar snittet av språken L(A₁) och L(A₂′):

Källor

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