# juxtaposition of automata

Let $A=(S_{1},\Sigma_{1},\delta_{1},I_{1},F_{1})$ and $B=(S_{2},\Sigma_{2},\delta_{2},I_{2},F_{2})$ be two automata. We define the juxtaposition of $A$ and $B$, written $AB$, as the sextuple $(S,\Sigma,\delta,I,F,\epsilon)$, as follows:

1. 1.

$S:=S_{1}\lx@stackrel{{\scriptstyle\cdot}}{{\cup}}S_{1}$, where $\lx@stackrel{{\scriptstyle\cdot}}{{\cup}}$ denotes disjoint union,

2. 2.

$\Sigma:=(\Sigma_{1}\cup\Sigma_{2})\lx@stackrel{{\scriptstyle\cdot}}{{\cup}}\{\epsilon\}$,

3. 3.

$\delta:S\times\Sigma\to P(S)$ given by

• $\delta(s,\epsilon):=I_{2}$ if $s\in F_{1}$, and $\delta(s,\epsilon):=\{s\}$ otherwise,

• $\delta|(S_{1}\times\Sigma_{1}):=\delta_{1}$,

• $\delta|(S_{2}\times\Sigma_{2}):=\delta_{2}$, and

• $\delta(s,\alpha):=\varnothing$ otherwise (where $\alpha\neq\epsilon$).

4. 4.

$I:=I_{1}$,

5. 5.

$F:=F_{2}$.

Because $S_{1}$ and $S_{2}$ are considered as disjoint subsets of $S$, $I\cap F=\varnothing$. Also, from the definition above, we see that $AB$ is an automaton with $\epsilon$-transitions (http://planetmath.org/AutomatonWithEpsilonTransitions).

The way $AB$ works is as follows: a word $c=ab$, where $a\in\Sigma_{1}^{*}$ and $b\in\Sigma_{2}^{*}$, is fed into $AB$. $AB$ first reads $a$ as if it were read by $A$, via transition function $\delta_{1}$. If $a$ is accepted by $A$, then one of its accepting states will be used as the initial state for $B$ when it reads $b$. The word $c$ is accepted by $AB$ when $b$ is accepted by $B$.

Visually, the state diagram $G_{A_{1}A_{2}}$ of $A_{1}A_{2}$ combines the state diagram $G_{A_{1}}$ of $A_{1}$ with the state diagram $G_{A_{2}}$ of $A_{2}$ by adding an edge from each final node of $A_{1}$ to each of the start nodes of $A_{2}$ with label $\epsilon$ (the $\epsilon$-transition).

###### Proposition 1.

$L(AB)=L(A)L(B)$

###### Proof.

Suppose $c=ab$ is a words such that $a\in\Sigma_{1}^{*}$ and $b\in\Sigma_{2}^{*}$. If $c\in L(AB)$, then $\delta(q,a\epsilon b)\cap F\neq\varnothing$ for some $q\in I=I_{1}$. Since $\delta(q,a\epsilon b)\cap F_{2}=\delta(q,a\epsilon b)\cap F\neq\varnothing$ and $b\in\Sigma_{2}^{*}$, we have, by the definition of $\delta$, that $\delta(q,a\epsilon b)=\delta(\delta(q,a\epsilon),b)=\delta_{2}(\delta(q,a% \epsilon),b)$, which shows that $b\in L(B)$ and $\delta(q,a\epsilon)\cap I_{2}\neq\varnothing$. But $\delta(q,a\epsilon)=\delta(\delta(q,a),\epsilon)$, by the definition of $\delta$ again, we also have $\delta(q,a)\cap F_{1}\neq\varnothing$, which implies that $\delta(q,a)=\delta_{1}(q,a)$. As a result, $a\in L(A)$.

Conversely, if $a\in L(A)$ and $b\in L(B)$, then for any $q\in I=I_{1}$, $\delta(q,a)=\delta_{1}(q,a)$, which has non-empty intersection with $F_{1}$. This means that $\delta(q,a\epsilon)=\delta(\delta(q,a),\epsilon)=I_{2}$, and finally $\delta(q,a\epsilon b)=\delta(\delta(q,a\epsilon),b)=\delta(I_{2},b)$, which has non-empty intersection with $F_{2}=F$ by assumption. This shows that $a\epsilon b\in L((AB)_{\epsilon})$, or $ab\in L(AB)$. ∎

Title juxtaposition of automata JuxtapositionOfAutomata 2013-03-22 18:03:51 2013-03-22 18:03:51 CWoo (3771) CWoo (3771) 14 CWoo (3771) Definition msc 03D05 msc 68Q45