## You are here

Homeproduct of automata

## Primary tabs

# 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}).$ |

## Mathematics Subject Classification

03D05*no label found*68Q45

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections