product of automata

One way to manufacture an automaton out of existing automata is by taking products.

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