juxtaposition of automata
Let $A=({S}_{1},{\mathrm{\Sigma}}_{1},{\delta}_{1},{I}_{1},{F}_{1})$ and $B=({S}_{2},{\mathrm{\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,\mathrm{\Sigma},\delta ,I,F,\u03f5)$, as follows:

1.
$S:={S}_{1}\stackrel{\cdot}{\cup}{S}_{1}$, where $\stackrel{\cdot}{\cup}$ denotes disjoint union^{},

2.
$\mathrm{\Sigma}:=({\mathrm{\Sigma}}_{1}\cup {\mathrm{\Sigma}}_{2})\stackrel{\cdot}{\cup}\{\u03f5\}$,

3.
$\delta :S\times \mathrm{\Sigma}\to P(S)$ given by

–
$\delta (s,\u03f5):={I}_{2}$ if $s\in {F}_{1}$, and $\delta (s,\u03f5):=\{s\}$ otherwise,

–
$\delta ({S}_{1}\times {\mathrm{\Sigma}}_{1}):={\delta}_{1}$,

–
$\delta ({S}_{2}\times {\mathrm{\Sigma}}_{2}):={\delta}_{2}$, and

–
$\delta (s,\alpha ):=\mathrm{\varnothing}$ otherwise (where $\alpha \ne \u03f5$).

–

4.
$I:={I}_{1}$,

5.
$F:={F}_{2}$.
Because ${S}_{1}$ and ${S}_{2}$ are considered as disjoint subsets of $S$, $I\cap F=\mathrm{\varnothing}$. Also, from the definition above, we see that $AB$ is an automaton with $\u03f5$transitions (http://planetmath.org/AutomatonWithEpsilonTransitions).
The way $AB$ works is as follows: a word $c=ab$, where $a\in {\mathrm{\Sigma}}_{1}^{*}$ and $b\in {\mathrm{\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 $\u03f5$ (the $\u03f5$transition).
Proposition 1.
$L(AB)=L(A)L(B)$
Proof.
Suppose $c=ab$ is a words such that $a\in {\mathrm{\Sigma}}_{1}^{*}$ and $b\in {\mathrm{\Sigma}}_{2}^{*}$. If $c\in L(AB)$, then $\delta (q,a\u03f5b)\cap F\ne \mathrm{\varnothing}$ for some $q\in I={I}_{1}$. Since $\delta (q,a\u03f5b)\cap {F}_{2}=\delta (q,a\u03f5b)\cap F\ne \mathrm{\varnothing}$ and $b\in {\mathrm{\Sigma}}_{2}^{*}$, we have, by the definition of $\delta $, that $\delta (q,a\u03f5b)=\delta (\delta (q,a\u03f5),b)={\delta}_{2}(\delta (q,a\u03f5),b)$, which shows that $b\in L(B)$ and $\delta (q,a\u03f5)\cap {I}_{2}\ne \mathrm{\varnothing}$. But $\delta (q,a\u03f5)=\delta (\delta (q,a),\u03f5)$, by the definition of $\delta $ again, we also have $\delta (q,a)\cap {F}_{1}\ne \mathrm{\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\u03f5)=\delta (\delta (q,a),\u03f5)={I}_{2}$, and finally $\delta (q,a\u03f5b)=\delta (\delta (q,a\u03f5),b)=\delta ({I}_{2},b)$, which has nonempty intersection with ${F}_{2}=F$ by assumption^{}. This shows that $a\u03f5b\in L({(AB)}_{\u03f5})$, or $ab\in L(AB)$. ∎
Title  juxtaposition of automata 

Canonical name  JuxtapositionOfAutomata 
Date of creation  20130322 18:03:51 
Last modified on  20130322 18:03:51 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  14 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D05 
Classification  msc 68Q45 