Cartesian Product Construction

Let $M,M^{\prime }$ be DFSA where:

• $M=(Q,\Sigma ,\delta ,s,F)$
• $M^{\prime }=(Q^{\prime },\Sigma ,{\delta }^{\prime },s^{\prime },F^{\prime })$ Want $M_{\cap }=(Q_{\cap },\Sigma ,{\delta }_{\cap },s_{\cap },F_{\cap }$ s.t $\mathcal{L}(M_{\cap })=\mathcal{L}(M)\cap \mathcal{L}(M^{\prime })$ Where:
• $Q_{\cap }=Q\times Q^{\prime }=\{(q,q^{\prime })|q\in Q,q^{\prime }\in Q^{\prime }\}$ (State Space Cartesian Product)
• ${\delta }_{\cap }((q,q^{\prime }),c)=(\delta (q,c),\delta (q^{\prime },c))$
• $s_{\cap }=(s,s^{\prime })$
• $F_{\cap }=F\times F^{\prime }$

Properties

• $M_{\cap }$ is a DFSA

Example

• Cartesian Product Construction Example