Nous allons à présent assouplir davantage la notion d'automate en permettant des transitions par le mot vide.
Définition
Un
automate d'état finis à \( \varepsilon\) -transition \( \A\) , plus simplement appelé AEF\( \varepsilon\) , est la donnée de
- \( \bullet\)
- un alphabet \( \Sigma_\A\) , appelé l'alphabet de l'automate,
- \( \bullet\)
- un ensemble fini \( E_\A\) d'état,
- \( \bullet\)
- un ensemble \( I_\A\subset E_\A\) d'états initiaux,
- \( \bullet\)
- un ensemble \( F_\A\subset E_\A\) d'états finaux,
- \( \bullet\)
- une fonction de transition \( \tau_\A : E_\A\times {\Sigma_\A\cup{\varepsilon}} \longrightarrow \mathcal{E_\A}\) .
En définitive, c'est exactement la même définition que pour un automate à ceci près que la fonction de transition, permet des transitions par le mot \( \varepsilon\) .
Exemple
Comme pour les ADEF et les AEF, on représente les AEF\( \varepsilon\) par une matrice ou un graphe augmenté.
\[
M_\A =
\begin{array}{c|ccc}
& 0 & 1 & \varepsilon\\\hline
X & X, Y & Y & Z\\
\rightarrow Y & X & Z & \\
Z\rightarrow & Y & Y, Z &
\end{array}
\]
\[
\xymatrix@C=2cm@R=1.19cm{
Y\ar@{{<}-}[d]\ar@/^0.519pc/[rd]^0\ar@/^0.519pc/[rr]^1&&Z\ar[d]\ar@/^0.519pc/[ll]^{0, 1}\ar@(lu, ru)[]^1\\
&X\ar@(dl, dr)[]_{0}\ar@/^0.519pc/[lu]^{0, 1}\ar@*{[red]}[ur]_{\color{red}\varepsilon}&
}
\]
Proposition
Tout AEF est un AEF\( \varepsilon\) .
Démonstration
Trivial.
L'idée à présent est de supprimer les \( \varepsilon\) -transition (pour qu'il n'y ai pas d'ambiguïté sur les mots reconnus - nous détaillerons ce point au prochain chapitre) et donc de transformer un AEF\( \varepsilon\) en AEF.
Définition
Soit \( \A\) une AEF\( \varepsilon\) et \( X\) un état de \( \A\) . On définit \( \overline{X}\) , la \( \varepsilon\) -clôture de \( X\) comme l'ensemble des états qui lisent le mot vide.
\[\overline{X} = \left\{Y\in E_\A \Big| \tau_\A(X, \varepsilon) = Y \right\}\]
La notion de
lecture sera détailler dans le prochain chapitre.
Exemple
Avec l'automate précédent, on a
\[\overline{X}=\{X, Z\}\qquad
\overline{Y}=\{Y\}\qquad
\overline{Z}=\{Z\}\]
Définition
Soit \( \A\) un AEF\( \varepsilon\) . L'automate
\( \varepsilon\) -libéré \( \A_\varepsilon\) est l'AEF définit par les règles suivantes :
- \( \bullet\)
- \( \Sigma_{\A_\varepsilon}=\Sigma_\A\)
- \( \bullet\)
- \( E_{\A_\varepsilon}=E_\A\)
- \( \bullet\)
- \( I_{\A_\varepsilon}=I_\A\)
- \( \bullet\)
- \( F_{\A_\varepsilon}=\left\{X\in E_{\A_\varepsilon} \Big| \overline{X}\cap F_\A\neq\varnothing\right\}\)
- \( \bullet\)
- La fonction de transition
\begin{eqnarray*}
\tau_{\A_\varepsilon} : E_{\A_\varepsilon} \times \Sigma_{\A_\varepsilon} & \longrightarrow & \mathcal{P}(E_{\A_\varepsilon})\\
(X, x) &\longmapsto&\bigcup_{Y\in\overline{X}}\tau_{\A}(Y, x)\\
\end{eqnarray*}
Exemple
Avec l'automate précédent on a
\[
M_{\A_\varepsilon} =
\begin{array}{c|cc}
& 0 & 1 \\\hline
X\rightarrow & X, Y & Y, Z \\
\rightarrow Y & X & Z \\
Z\rightarrow & Y & Y, Z
\end{array}
\]
Exercice
Déterminer l'automate \( \varepsilon\) -libéré de chacun des AEF\( \varepsilon\) suivant.
- \( \begin{array}{c|*{4}{c}} & x & y &\varepsilon \\ \hline A & A & A, B, C & \\ \rightarrow B \rightarrow & A & A, C &\\ C & A, B, C & A, B & A\\ \end{array}\)
- \( \begin{array}{c|*{5}{c}} & x & y &\varepsilon \\ \hline A \rightarrow & A, C & A, C & A, C\\ B & A, B, C, D & A, C, D & \\ \rightarrow C & A, B, C, D & C, D \\ D & D & A, B & C\\ \end{array}\)
- \( \begin{array}{c|*{5}{c}} & \alpha & \beta & \gamma & \varepsilon \\ \hline A & A, C & B & A, C &\\ B \rightarrow & A, B, C & B, C & C, D & B, D\\ \rightarrow C & A, C & D & A, C, D &\\ D & A, C, D & D & B, C &\\ \end{array}\)
- \( \begin{array}{c|*{4}{c}} & 0 & 1 & 2 &\varepsilon \\ \hline A & C & A, B, C & C & A, C\\ \rightarrow B \rightarrow & B, C & A, B, C & B & B\\ C & A, B, C & C & A & B\\ \end{array}\)
