You are here
Homejuxtaposition of automata
Primary tabs
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. $S:=S_{1}\stackrel{\cdot}{\cup}S_{1}$, where $\stackrel{\cdot}{\cup}$ denotes disjoint union,
2. $\Sigma:=(\Sigma_{1}\cup\Sigma_{2})\stackrel{\cdot}{\cup}\{\epsilon\}$,
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. $I:=I_{1}$,
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.
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 nonempty 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 nonempty intersection with $F_{2}=F$ by assumption. This shows that $a\epsilon b\in L((AB)_{{\epsilon}})$, or $ab\in L(AB)$. ∎
Mathematics Subject Classification
03D05 no label found68Q45 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