The difference of regular languages

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

Idea

There's not really much to prove. In fact, the following relation holds for the difference of two sets:

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

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

Example

Let's have this automaton A₁, which accepts all words that contain an even number of 1's:

and an automaton A₂, which accepts words containing an odd number of 0:

We construct an automaton that accepts the difference of these languages. Thus we need an automaton $A_2^\prime$, which will be complementary to the automaton A₂. We just swap the end and non-end states:

Now we just construct an automaton A, which will accept the intersection of the languages L(A₁) and $L(A_2^\prime)$:

Sources

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