CS 373: Theory of Computation Madhusudan Parthasarathy
Lecture 4: The product construction: Closure un- der intersection and union
28 January 2010
This lecture nishes section 1.1 of Sipser and also covers the start of 1.3.
1 Product Construction
1.1 Product Construction: Example
Let Σ = {a,b} and L is the set of strings in Σ∗ that have the form a∗b∗ and have even length. L is the intersection of two regular languages L1 = a∗b∗ and L2 = (ΣΣ)∗. We can show they are regular by exhibiting DFAs that recognize them.
a,b q0 b q1 a drain
r0
r1 L2
ab
a,b
a,b
L1
We can run these two DFAs together, by creating states that remember the states of both
machines.
(q0, r0) (q1, r0) (drain, r0) baa
a ab b b a,b a,b (q0, r1) (q1, r1) (drain, r1)
Notice that the nal states of the new DFA are the states (q, r) where q is nal in the rst DFA and r is nal in the second DFA. To recognize the union of the two languages, rather than the intersection, we mark all the states (q, r) such that either q or r are accepting states in the their respective DFAs.
State of a DFA after reading a word w. In the following, given a DFA M = (Q, Σ, δ, q0, F ), we will be interested in the state the DFA M is in, after reading the a string w. Let us denote
1
by δ∗ : Q × Σ∗ → Q the function such that δ∗(q,w) is the state the DFA will land in, if started from state q and fed the word w.
Formally, we dene δ∗ : Q × Σ∗ → Q using the following inductive denition:
• δ∗(q,ε)=qforeveryq∈Q,
• δ∗(q,wa) = δ(δ∗(q,w),a) for each q ∈ Q,w ∈ Σ∗,a ∈ Σ.
Note that by the above denition of δ∗, we have that w ∈ L(M) i δ∗(q0,w) ∈ F.
2 Product Construction: Formal construction
We are given two DFAs M = (Q,Σ,δ,q0,F) and M′ = (Q′,Σ,δ′,q0′ ,F′) both working over
the same alphabet Σ. A product automaton of M and M′ is an automaton N=Q,Σ,δ ,(q,q′),F,
N00N
whereQ=Q×Q′,andδN :Q×Σ→Q. Also,foranyq∈Q,q′ ∈Q′ andc∈Σ,werequire
δN( (q,q′) ,c ) =δ(q,c), δ′(q′,c). (1)
state of N
The set FN ⊆ Q of accepting states is free to be whatever we need it to be, depending on what we want N to recognize. For example, if we would like N to accept the intersection L(M)∩L(M′) then we will set FN = F ×F′. If we want N to recognize the union language L(M)∪L(M′) then FN =(F ×Q′) ∪ ∪(Q×F′).
Lemma 2.1 For any input word w ∈ Σ∗, the product automata N of the DFAs M = (Q,Σ,δ,q0,F) and M′ = (Q′,Σ,δ′,q0′,F′), is in state (q,q′) after reading w, if and only if (i) M in the state q after reading w, and (ii) M′ is in the state q′ after reading w. In other words, δN∗ ((q0, q0′ ), w) = (δ∗(q0, w), δ′∗(q0′ , w)).
Proof: The proof is by induction on the length of the word w.
If w = ε is the empty word, then N is initially in the state (q0, q0′ ) by construction, where q0 (resp. q0′ ) is the initial state of M (resp. M′). As such, the claim holds in this case.
Formally, δN∗ ((q0, q0′ ), ε) = (q0, q0′ ) = (δ∗(q0, ε), δ′∗(q0′ , ε)) (by denition of δN∗ , δ∗ and δ′∗).
Otherwise, |w| > 0, and let us hence assume w = w1a (w1 ∈ Σ∗, a ∈ Σ), and assume the induction hypothesis that the claim is true for all input words of length strictly smaller than |w| (in particular |w1|).
Let (qk−1, qk′ −1) be the state that N is in after reading the string w1. By the induction hypothesis, as |w1| = k − 1, we know that M is in the state qk−1 after reading w, and M′ is in the state qk′ −1 after reading w.
Let qk = δ(qk−1, a) = δ(δ∗(q0, w1) , a) = δ(q0, w) and
q′ = δ′(q′ ,a) = δ′(δ′(q′ ,w ), a) = δ′(q′ ,w).
kk−1 01 0 2
As such, by denition, M (resp. M′) would in the state qk (resp. qk′ ) after reading w.
Also, by the denition of its transition function, after reading w the DFA N would be in
the state
δ ((q ,q′),w)=δ (δ∗ ((q ,q′),w ),a)=δ (q ,q′
N 0 0 N N 0 0 1 N k−1 k−1
,a), δ(q′ ,a) =(q , q′ ), k−1 k k
), a
=δ(q
(see Eq. (1)). This establishes the claim.
k−1
Lemma 2.2 Let M = (Q,Σ,δ,q0,F) and M′ = (Q′,Σ,δ′,q0′ ,F′) be two given DFAs. Let N be a product automaton with set of accepting states is F ×F′. Then L(N) = L(M)∩L(M′).
Proof: w∈L(N)iδN∗ ((q0,q0′),w)∈F×F′
i (δ∗(q0, w), δ′∗(q0′ , w)) ∈ F × F ′ (by Lemma 2.1)
i δ∗(q0,w) ∈ F and δ′∗(q0′ ,w) ∈ F′ i w ∈ L(M) and w ∈ L(M′).
More verbosely:
If w ∈ L(M)∩L(M′), then let qw = δ∗(q0,w) ∈ F and qw′ = δ′∗(q0′,w) ∈ F′. By Lemma 2.1, this implies that δN∗ ((q0,q0′),w) = (qw,qw′ ) ∈ F ×F′. Namely, N accepts the word w, implying that w ∈ L(N), and as such L(M) ∩ L(M′) ⊆ L(N).
Similarly, if w ∈ L(N), then (pw,p′w) = δN∗ ((q0,q0′),w) must be an accepting state of N. But the set of accepting states of N is F × F′. That is (pw,p′w) ∈ F × F′, implying thatpw ∈F andp′w ∈F′. Now,byLemma2.1,weknowthatδ∗(q0,w)=pw ∈F and δ′∗(q0′ ,w) = p′w ∈ F′. Thus, M and M′ both accept w, which implies that w ∈ L(M) and w ∈ L(M′). Namely, w ∈ L(M) ∩ L(M′), implying that L(N) ⊆ L(M) ∩ L(M′).
Putting the above together proves the lemma.
3