Intersection of regular languages

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

The idea of the proof

We have two regular languages L₁ and L₂ and we want to prove that their intersection L₁ ∩ L₂ is again a regular language. Since L₁ and L₂ are regular languages, there are finite automata A₁ and A₂ that accept the languages L₁ and L₂, so L(A₁) = L₁ and L(A₂) = L₂. We will now construct a finite automaton A that accepts the language L₁ ∩ L₂, which proves that the language L₁ ∩ L₂ is regular.

A string belongs to the intersection of the languages if it belongs to both L₁ and L₂. So the string must be accepted by the automaton A₁ and at the same time by the automaton A₂. We use exactly the same idea as we used for the union of regular languages; we only change the set of accepting states.

Formalisation of the procedure

We have two automata,

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

We construct an automaton A = ⟨Q, Σ, δ, q, F⟩ that accepts the language L(A₁) ∩ L(A₂). Here

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

For the transition function δ the following holds:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

Example

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

and the automaton A₂, which accepts strings containing an odd number of 0s:

We construct an automaton that accepts the intersection of these languages. The set of states of this automaton has the form Q = Q₁ × Q₂, the start state is ⟨q₀, p₀⟩ and the accepting states are F₁ × F₂:

Next we complete the transitions so that δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

In this automaton, for example, from the state ⟨q₀, p₀⟩ there is a transition on the symbol 0 to the state ⟨q₀,p₁⟩. This means that the automaton A₁ has a transition on the symbol 0 from the state q₀ back to q₀. The automaton A₂, in turn, has a transition on the symbol 0 from the state p₀ to the state p₁.

We can try the automaton out. It should accept strings such as 110 or 00000 (they contain an even number of 1s and at the same time an odd number of 0s), but it should not accept strings such as 11, 111, 1010.

Sources

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