The intersection of regular languages
Kapitoly: Closure of regular languages, Unification, Access, The Difference, Supplement, Concatenation, Conclusion
Let us have two regular languages L1, L2. We prove that their intersection L = L1 ∩ L2 is also a regular language.
The idea of a proof
Given two regular languages L1 and L2, we want to prove that their intersection L1 ∩ L2 is again a regular language. Since L1 and L2 are regular languages, there are finite automata A1 and A2, which accept the languages L1 and L2, so L(A1) = L1 and L(A2) = L2 hold. We next construct a finite automaton A, which accepts the language L1 ∩ L2, proving that the language L1 ∩ L2 is regular.
A word belongs to the intersection of languages if it belongs to the language L1 and also L2. Thus, the word must be accepted by the automaton A1 and also by the automaton A2. We will use exactly the same idea as we used in the unification of regular languages, only we will change the set of finite states.
Formalizing the procedure.
We have two automata,
\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right>\A_2&=&\left<Q_2, \Sigma_2, \delta_2, p_0, F_2\right> \end{eqnarray}
We construct an automaton $A=\left<Q, \Sigma, \delta, q, F\right>$, which accepts the language L(A1)∩ L(A2). It holds that
- Q = Q1 × Q2
- $\Sigma = \Sigma_1 \cap \Sigma_2$
- q = <q0, p0>
- F = F1 × F2
The following relation will hold for the transition function δ:
$$ \forall q\in Q_1, p\in Q_2: \delta(\left<q,p\right>, a) = \left<\delta_1(q, a), \delta_2(p, a)\right> $$
Example
Consider this automaton A1, which accepts all words that contain an even number of 1:
and the automaton A2, which accepts words containing an odd number of 0:
Construct an automaton that accepts the intersection of these languages. The set of states of this automaton is of the form Q = Q1 × Q2, the initial state is the state <q0, p0>, and the final states are F1 × F2:
Next, we complete the transitions such that δ(<q,p>, a) = <δ1(q, a), δ2(p, a)>:
For example, in this automaton, the state <q0, p0> is the transition for symbol 0 to the state <q0,p1>. This means that the automaton A1 has a transition for symbol 0 from the state q0 back to the state q0. The automaton A2 in turn has a transition for symbol 0 from the state p0 to the state p1.
We can test the automaton. It should accept words like 110 or 00000 (they contain an even number of 1s and an odd number of 0s), but it should not accept words like 11, 111, 1010).