Differens af regulære sprog

Vi har to regulære sprog L₁, L₂. Vi viser, at deres differens L = L₁ ∖ L₂ også er et regulært sprog.

Idé

Egentlig er der ikke meget at bevise. For differensen af to mængder gælder nemlig følgende sammenhæng:

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

hvor L₂′ er komplementet til sproget L₂. Fra afsnittene om fællesmængde af regulære sprog og komplement af et regulært sprog ved vi, at regulære sprog er lukkede under begge disse operationer. Det betyder, at vi kan konstruere en automat, som accepterer fællesmængden af sprog, og en automat, som accepterer komplementet til et sprog. Disse automater kan vi derfor bruge til at konstruere en automat, som accepterer sproget L₁ ∩ L₂′, og det er samtidig sproget L₁ ∖ L₂.

Eksempel

Vi ser på denne automat A₁, som accepterer alle ord, der indeholder et lige antal 1'ere:

og automaten A₂, som accepterer ord, der indeholder et ulige antal 0'er:

Vi konstruerer en automat, som accepterer differensen af disse sprog. Vi har derfor brug for en automat A₂′, som er komplementet til automaten A₂. Vi bytter blot om på accepttilstande og ikke-accepterende tilstande:

Nu mangler vi blot at konstruere automaten A, som accepterer fællesmængden af sprogene L(A₁) og L(A₂′):

Kilder

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