Difference of regular languages

Let L₁, L₂ be two regular languages. We will prove that their difference L = L₁ ∖ L₂ is also a regular language.

Idea

There is really not much to prove. For the difference of two sets, the following relation holds:

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

where $L_2^c$ is the complement of the language L₂. From the chapters on the intersection of regular languages and the complement of a regular language, we know that regular languages are closed under both of these operations. This means that we can construct an automaton that accepts the intersection of languages and an automaton that accepts the complement of a language. We can therefore use these automata to construct an automaton that accepts the language $L_1\cap L_2^c$, which is at the same time the language L₁ ∖ L₂.

Example

Let A₁ be this automaton, which accepts all strings that contain an even number of 1s:

and let A₂ be an automaton that accepts strings containing an odd number of 0s:

We will construct an automaton that accepts the difference of these languages. We need an automaton $A_2^c$, which will be the complement of the automaton A₂. We just swap the accepting and non-accepting states:

Now we only need to construct the automaton A, which will accept the intersection of the languages L(A₁) and $L(A_2^c)$:

Sources

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