Algorithm:Intersection
Input: DFA M1 = (Q1,Σ,δ1,s1,W1) and DFA M2 = (Q2,Σ,δ2,s2,W2)
Output: DFA M such that L(M) = L(M1) ∩ L(M2)
M = (Q,Σ,δ,s,W), where
- Q = Q1 x Q2
- δ:Q x Σ → Q
δ((q,p),a) = (δ1(q,a),δ2(p,a))- s = (s1,s2)
- W = W1 x W2
Theorem: Algorithm Intersection meets its
specification, i.e.
L(M) = L(M1) ∩ L(M2).
Proof:
The idea behind the algorithm is that a computation in M is
supposed to simulate computations in M1 and M2 simultaneously.
We make that precise with the following lemma (little
theorem) that shows that one step of computation in M is
equivalent to one step from M1 and one step from M2 simultaneously.
Lemma:
$((p_1,p_2),u) \Rightarrow_M ((q_1,q_2),v)$
if and only if
$(p_1,u) \Rightarrow_{M_1} (q_1,v)$ and
$(p_2,u) \Rightarrow_{M_2} (q_2,v)$.
Proof: By the defintion of $\Rightarrow_M$ we have where $u = xv$, $x \in \Sigma$.
Proof: By the defintion of $\Rightarrow_M$ we have where $u = xv$, $x \in \Sigma$.
-
Suppose $((p_1,p_2),u) \Rightarrow_M ((q_1,q_2),v)$,
then ...
$\delta((p_1,p_2),x) = (q_1,q_2)$, so $\delta_1(p_1,x) = q_1$ and $\delta_2(p_2,x) = q_2$, which means $(p_1,u) \Rightarrow_{M_1} (q_1,v)$ and $(p_2,u) \Rightarrow_{M_2} (q_2,v)$.
-
Suppose
$(p_1,u) \Rightarrow_{M_1} (q_1,v)$ and
$(p_2,u) \Rightarrow_{M_2} (q_2,v)$,
then ...
$\delta_1(p_1,x) = q_1$ and $\delta_2(p_2,x) = q_2$, so $\delta((p_1,p_2),x) = (q_1,q_2)$, which means $((p_1,p_2),u) \Rightarrow_M ((q_1,q_2),v)$.
To prove our theorem, we need to show that $w \in L(M)$ if and only if $w \in L(M1)$ and $w \in L(M2)$. That means two parts:
- Part 1: Show that if $w\in L(M)$ then $w \in L(M1)$ and $w \in L(M2)$.
Since $w \in L(M)$, we know that \[ ((p_1,q_1),w_1) \Rightarrow_M ((p_2,q_2),w_2) \Rightarrow_M \cdots \Rightarrow_M ((p_k,q_k),\lambda) \] where $w = w_1$ and $p_1 = s1$ and $q_1 = s2$ and $p_k \in W_1$ and $q_k \in W_2$. Applying the lemma to each $\Rightarrow_M$ we get that the following is a computation in $M1$ \[ (p_1,w_1) \Rightarrow_{M1} (p_2,w_2) \Rightarrow_{M1} \cdots \Rightarrow_{M1} (p_k,\lambda) \] which means $w \in L(M1)$, and in $M2$ we have the computation \[ (q_1,w_1) \Rightarrow_{M2} (q_2,w_2) \Rightarrow_{M2} \cdots \Rightarrow_{M2} (q_k,\lambda) \] which means $w \in L(M2)$. - Part 2: Show that if $w \in L(M1)$ and $w \in L(M2)$ then $w\in L(M)$.
The proof of this is just the reverse of the "Part 1" argument. This works because our lemma is "if and only if".
The most sincere comment I can make about degrees of proof is this: when you're really convinced, that's enough detail. This, of course, requires that you are sincere in evaluating when you're convinced. Hopefully, with the algorithms we've done so far you were convinced when you truly understood how the algorithm worked. Further proof, like the one above, probably seemed pointless. That's why I'm going to put most of the emphasis on the higher level view of understanding the algorithms. However, be aware that it's easy to convince yourself of things that aren't true, so there is value in getting down to all the details and working out every last one. When that's been done, you're really sure.
Now, what does this machine do? It accepts the language of all strings over {a,b,c} that start with a c and have an even number of a's and b's.
(q0,cacbcc) => (q1,acbcc) => (q2,cbcc) => (q2,bcc) => (q1,cc) => (q1,c) => (q1,λ) (q0,cacbcc) => (q1,acbcc) => (q2,cbcc) => (q2,bcc) => (q1,cc) => (q1,c) => (q3,λ) (q0,cacbcc) => (q1,acbcc) => (q2,cbcc) => (q2,bcc) => (q1,cc) => (q2,c) => stuckOnly the second of these actually accepts the string (which, by my description, we'd really like to accept). So, computation by a machine like this is non-deterministic, i.e. we can't tell exactly what the computation will be for every input. Still, can we come up with a sensible definition of what strings such a machine accepts and what strings it rejects? How about this:
A non-deterministic finite automaton accepts a string if there is a way for it to end up in an accepting state. Only if there is no way for it to end up in an accepting state does it reject its input string. Another way to view this is to say that the machine always makes lucky guesses about which transition to take when there is more than one possiblity.This is a definition that makes sense for M2, and would makes sense for any non-deterministic machine. Now, to tidy up a bit we have to admit that M2 doesn't do exactly what it's supossed to, because it doesn't accept the string c, which is indeed a string that starts and ends with c and contains an even number of a's and b's. The following machine, M3, fixes this:
(q0,cacc) => (q1,cacc) => (q3,acc) => (q5,cc) => (q5,c) => (q5,λ) (q0,cacc) => (q2,cacc) => (q2,acc) => (q2,cc) => (q2,c) => (q4,λ) (q0,cacc) => (q2,cacc) => (q2,acc) => (q2,cc) => (q4,c) => STUCK (q0,cacc) => (q2,cacc) => (q4,acc) => STUCKSince one of these computations (the second one) leaves us in an accepting state, the string is accepted!
- have a state/symbol combination with no defined transition,
- have a state/symbol combination with transitions to more than one state, and
- have λ-transitions, i.e. transitions the machine can take without reading an input symbol.
Important! A non-deterministic machine accepts a string as long as there is some way that it can process the string and end up in an accepting state.