Définition
Soient \( \A\) et \( \mathscr{B}\) deux automates sur un alphabet \( \Sigma\) où l'on renomme les états de \( \mathscr{B}\) de sorte que \( E_\A\cap E_{\mathscr{B}}=\varnothing\) .
On définit \( \A\mathscr{B}\) l'automate à \( \varepsilon\) -transition, par les règles suivantes.
- \( \bullet\)
- \( \Sigma_{\A\mathscr{B}}=\Sigma\)
- \( \bullet\)
- \( E_{\A\mathscr{B}}=E_\A\cup E_{\mathscr{B}}\)
- \( \bullet\)
- \( I_{\A\mathscr{B}}=I_\A\)
- \( \bullet\)
- \( F_{\A\mathscr{B}}=F_\mathscr{B}\)
- \( \bullet\)
- La fonction de transition
\begin{eqnarray*}
\tau_{\A\mathscr{B}} : E_{\A\mathscr{B}} \times \Sigma\cup{\varepsilon} & \longrightarrow & \mathcal{P}\left(E_{\A\mathscr{B}}\right)\\
\forall A \in E_\A, \forall x\in \Sigma, \
(A, x) &\longmapsto&\tau_\A(A, x)\\
\forall B \in E_\mathscr{B}, \forall x\in \Sigma,\
(B, x) &\longmapsto&\tau_\mathscr{B}(B, x)\\
\forall f\in F_\A, \forall i \in I_\mathscr{B},\ (f, \varepsilon)&\longmapsto i
\end{eqnarray*}
En définitive, on
connecte, par une \( \varepsilon\) -transition, les deux automates que l'on souhaite concaténer.
Exemple
Sur l'alphabet \( \Sigma=\{a, b\}\) , considérons les automates reconnaissant chacun des caractères.
Automate reconnaissant \( \{a\}\) :
\[
\xymatrix{
\ar[r]&A\ar[rd]_{b}\ar[rr]^{a}&&B\ar[ld]^{a, b}\ar[r]&\\
&&C\ar@(ld, rd)[]_{a, b}&&
}
\]
\[
\begin{array}{c|cc}
&a&b\\\hline
\rightarrow A&B&C\\
B \rightarrow&C&C\\
C&C&C
\end{array}
\]
Automate reconnaissant \( \{b\}\) ; c'est le même que précédemment en changeant le rôle de \( a\) et \( b\) et en prenant soin de nommer les états différemment de ceux de l'automate précédent :
\[
\xymatrix{
\ar[r]&D\ar[rd]_{a}\ar[rr]^{b}&&E\ar[ld]^{a, b}\ar[r]&\\
&&F\ar@(ld, rd)[]_{a, b}&&
}
\]
\[
\begin{array}{c|cc}
&a&b\\\hline
\rightarrow D&F&E\\
E \rightarrow&F&F\\
F&F&F
\end{array}
\]
L'automate concatené est alors
\[
\xymatrix{
\ar[r]&A\ar[rd]_{b}\ar[rr]^{a}&&B\ar[ld]^{a, b}\ar@*{[red]}[rr]^{\color{red}\varepsilon}&
&D\ar[rd]_{a}\ar[rr]^{b}&&E\ar[ld]^{a, b}\ar[r]&\\
&&C\ar@(ld, rd)[]_{a, b}&&
&&F\ar@(ld, rd)[]_{a, b}&&
}
\]
Sa matrice est
\[
\begin{array}{c|ccc}
& a & b & \varepsilon\\\hline
\rightarrow A& B & C & \\
B& C & C & D \\
C& C & C & \\
D& F & E & \\
E\rightarrow& F & F & \\
F& F & F &
\end{array}
\]
dont l'\( \varepsilon\) -libéré est l'AEF
\[
\begin{array}{c|cc}
& a & b \\\hline
\rightarrow A& B & C \\
B& C, F & C, E \\
C& C & C \\
D& F & E \\
E\rightarrow& F & F \\
F& F & F
\end{array}
\]
dont l'automate déterministe associé est
\[
\begin{array}{c|cc}
& a & b \\\hline
\rightarrow \{A\}& \{B\} & \{C\} \\
\{B\}& \{C, F\} & \{C, E\} \\
\{C\}& \{C\} & \{C\} \\
\{C, F\} &\{C, F\}&\{C, F\}\\
\{C, E\} \rightarrow &\{C, F\}&\{C, F\}
\end{array}
\]
dont, pour y voir plus claire, nous pouvont renommer les états
\[
\begin{array}{c|cc}
& a & b \\\hline
\rightarrow U& V & W \\
V& X & Y \\
W& W & W \\
X &X&X\\
Y \rightarrow &X&X
\end{array}
\]
Proposition
Soient \( \A\) et \( \mathscr{B}\) deux automates.
\[L(\left(\A\mathscr{B}\right)_\varepsilon) = L(\A\mathscr{B})=L(\A)L(\mathscr{B})\]
Démonstration
C'est une conséquence triviale de la définition.
Exercice
Pour chacune des paires d'automates suivants \( \A\) et \( \mathscr{B}\) , déterminer l'ADEF, représentant la concaténation \( \A\mathscr{B}\) et \( \mathscr{B}\A\) .
-
\(
\A = \left(
\begin{array}{c|cc}
&a&b\\\hline
\rightarrow A\rightarrow &A&B\\
B &B&B
\end{array}\right)
\qquad
\mathscr{B} =\left(
\begin{array}{c|cc}
&a&b\\\hline
\rightarrow A&A&B\\
B\rightarrow &B&B
\end{array}\right)
\)
-
\(
\A = \left(
\begin{array}{c|cc}
&a&b\\\hline
\rightarrow A&B&A\\
B\rightarrow &B&A
\end{array}\right)
\qquad
\mathscr{B} =\left(
\begin{array}{c|cc}
&a&b\\\hline
\rightarrow A&C&B\\
B &B&B\\
C\rightarrow &C&B
\end{array}\right)
\)
