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,ϵ)$, 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 }\{ϵ\}$,

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

   • $\delta (s,ϵ):=I_2$ if $s\in F_1$, and $\delta (s,ϵ):=\{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 ϵ$).

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 $ϵ$-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 $ϵ$ (the $ϵ$-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ϵb)\cap F\ne \mathrm{\varnothing }$ for some $q\in I=I_1$. Since $\delta (q,aϵb)\cap F_2=\delta (q,aϵb)\cap F\ne \mathrm{\varnothing }$ and $b\in {\mathrm{\Sigma }}_2^{*}$, we have, by the definition of $\delta$, that $\delta (q,aϵb)=\delta (\delta (q,aϵ),b)={\delta }_2(\delta (q,aϵ),b)$, which shows that $b\in L(B)$ and $\delta (q,aϵ)\cap I_2\ne \mathrm{\varnothing }$. But $\delta (q,aϵ)=\delta (\delta (q,a),ϵ)$, 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 non-empty intersection with $F_1$. This means that $\delta (q,aϵ)=\delta (\delta (q,a),ϵ)=I_2$, and finally $\delta (q,aϵb)=\delta (\delta (q,aϵ),b)=\delta (I_2,b)$, which has non-empty intersection with $F_2=F$ by assumption. This shows that $aϵb\in L({(AB)}_{ϵ})$, or $ab\in L(AB)$. ∎

Title	juxtaposition of automata
Canonical name	JuxtapositionOfAutomata
Date of creation	2013-03-22 18:03:51
Last modified on	2013-03-22 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