# product of automata

## Products of Two Automata

Let $A_{1}=(S_{1},\Sigma_{1},\delta_{1},I_{1},F_{1})$ and $A_{2}=(S_{2},\Sigma_{2},\delta_{2},I_{2},F_{2})$ be two automata. We define the product $A$ of $A_{1}$ and $A_{2}$, written $A_{1}\times A_{2}$, as the quituple

 $(S,\Sigma,\delta,I,F):=(S_{1}\times S_{2},\Sigma_{1}\times\Sigma_{2},\delta_{1% }\times\delta_{2},I_{1}\times I_{2},F_{1}\times F_{2}),$

where $\delta$ is a function  from $S\times\Sigma$ to $P(S_{1})\times P(S_{2})\subseteq P(S)$, given by

 $\delta((s_{1},s_{2}),(\alpha_{1},\alpha_{2})):=\delta_{1}(s_{1},\alpha_{1})% \times\delta_{2}(s_{2},\alpha_{2}).$

Since $S,\Sigma,I,F$ are non-empty, $A$ is an automaton. The automaton $A$ can be thought of as a machine that runs automata $A_{1}$ and $A_{2}$ simultaneously. A pair $(\alpha_{1},\alpha_{2})$ of symbols being fed into $A$ at start state $(q_{1},q_{2})\in I$ is the same as $A_{1}$ reading $\alpha_{1}$ at state $q_{1}$ and $A_{2}$ reading $\alpha_{2}$ at state $q_{2}$. The set of all possible next states for the configuration  $((s_{1},s_{2}),(\alpha_{1},\alpha_{2}))$ in $A$ is the same as the set of all possible combinations   $(t_{1},t_{2})$, where $t_{1}$ is a next state for the configuration $(s_{1},\alpha_{1})$ in $A_{1}$ and $t_{2}$ is a next state for the configuration $(s_{2},\alpha_{2})$ in $A_{2}$.

If $A_{1}$ and $A_{2}$ are FSA, so is $A$. In addition, if both $A_{1}$ and $A_{2}$ are deterministic  , so is $A$, because

 $\delta((s_{1},s_{2}),(\alpha_{1},\alpha_{2}))=(\delta_{1}(s_{1},\alpha_{1}),% \delta_{2}(s_{2},\alpha_{2})),$

and $I$ is a singleton.

As usual, $\delta$ can be extended to read words over $\Sigma$, and it is easy to see that

 $\delta((s_{1},s_{2}),(a_{1},a_{2}))=\delta_{1}(s_{1},a_{1})\times\delta_{2}(s_% {2},a_{2}),$

where $a_{1}$ and $a_{2}$ are words over $\Sigma_{1}$ and $\Sigma_{2}$ respectively. A word $(a_{1},a_{2})$ is accepted by $A$ iff $a_{1}$ is accepted by $A_{1}$ and $a_{2}$ is accepted by $A_{2}$.

## Intersection of Two Automata

Again, we assume $A_{1}$ and $A_{2}$ are automata specified above. Now, suppose $\Sigma_{1}=\Sigma_{2}=\Delta$. Then $\Delta$ can be identified as the diagonal in $\Sigma=\Sigma_{1}\times\Sigma_{2}=\Delta^{2}$. We are then led to an automaton

 $A_{1}\cap A_{2}:=(S,\Delta,\delta,I,F),$

where $S,I$, and $F$ are defined previously, and $\delta$ is given by

 $\delta((s_{1},s_{2}),\alpha)=\delta_{1}(s_{1},\alpha)\times\delta_{2}(s_{2},% \alpha).$

Suppose in addition that $\Delta$ is finite. From the discussion in the previous section, it is evident that the language  accepted by $A_{1}\cap A_{2}$ is the same as the intersection   of the language accepted by $A_{1}$ and the language accepted by $A_{2}$:

 $L(A_{1}\cap A_{2})=L(A_{1})\cap L(A_{2}).$
Title product of automata ProductOfAutomata 2013-03-22 18:03:06 2013-03-22 18:03:06 CWoo (3771) CWoo (3771) 12 CWoo (3771) Definition msc 03D05 msc 68Q45