Proof (sketch): Suppose L_{1} and L_{2} are recognizable. Then there are DFAs A_{1} = (Q,Σ, T_{1}, q_{0}, F_{1}) and A_{2} = (P,Σ, T_{2}, p_{0}, F_{2}) such that L_{1} = L(A_{1}) and L_{2} = L(A_{2}). We construct A′ such that L(A′ ) = L_{1} ∩ L_{2}. The idea is to have A′ run A_{1} and A_{2} in parallel-keeping track of the state of both machines. It will accept a string, then, iff both machines reach an accepting state on that string.
Let A′ = (Q × P,Σ, T′ , (q_{0}, p_{0}), F_{1} × F_{2}), where
T′ def= [{((q, pi, (q′, p′), σ) | (q, q′, σi)∈ T_{1} and (p, p′, σ ∈ T_{2}}.
Then
(You should prove this; it is an easy induction on the structure of w.) It follows then that