# product of automata

## Products of Two Automata

Let ${A}_{1}=({S}_{1},{\mathrm{\Sigma}}_{1},{\delta}_{1},{I}_{1},{F}_{1})$ and ${A}_{2}=({S}_{2},{\mathrm{\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,\mathrm{\Sigma},\delta ,I,F):=({S}_{1}\times {S}_{2},{\mathrm{\Sigma}}_{1}\times {\mathrm{\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 \mathrm{\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,\mathrm{\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 $\mathrm{\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 ${\mathrm{\Sigma}}_{1}$ and ${\mathrm{\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 ${\mathrm{\Sigma}}_{1}={\mathrm{\Sigma}}_{2}=\mathrm{\Delta}$. Then $\mathrm{\Delta}$ can be identified as the diagonal in $\mathrm{\Sigma}={\mathrm{\Sigma}}_{1}\times {\mathrm{\Sigma}}_{2}={\mathrm{\Delta}}^{2}$. We are then led to an automaton

$${A}_{1}\cap {A}_{2}:=(S,\mathrm{\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 $\mathrm{\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 |
---|---|

Canonical name | ProductOfAutomata |

Date of creation | 2013-03-22 18:03:06 |

Last modified on | 2013-03-22 18:03:06 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 12 |

Author | CWoo (3771) |

Entry type | Definition |

Classification | msc 03D05 |

Classification | msc 68Q45 |