Définition
Soit \( \A\) un automate sur un alphabet \( \Sigma\) . On définit \( \A^*\) , l'automate a \( \varepsilon\) -transition, par les règles suivantes.
- \( \bullet\)
- \( \Sigma_{\A^*}=\Sigma\)
- \( \bullet\)
- \( E_{\A^*}=E_\A\)
- \( \bullet\)
- \( I_{\A^*}=I_\A\)
- \( \bullet\)
- \( F_{\A^*}=I_\A\)
- \( \bullet\)
- La fonction de transition
\begin{eqnarray*}
\tau_{\A^*} : E_{\A^*} \times \Sigma\cup{\varepsilon} & \longrightarrow & \mathcal{P}\left(E_{\A^*}\right)\\
\forall x \in \Sigma \
(E, x) &\longmapsto&\tau_\A(E, x)\\
\forall f\in F_\A, \forall i \in I_\A, \ (f, \varepsilon)&\longmapsto i
\end{eqnarray*}
Exemple
Sur l'alphabet \( \Sigma=\{a, b\}\) , considérons l'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}
\]
Alors l'automate étoile est
\[
\xymatrix{
\ar[r]&A\ar[d]\ar[rd]_{b}\ar[rr]^{a}&&B\ar[ld]^{a, b}\ar@*{[red]}@/_1pc/[ll]_{\color{red}\varepsilon}&\\
&&C\ar@(ld, rd)[]_{a, b}&&
}
\]
Sa matrice est
\[
\begin{array}{c|ccc}
&a&b&\varepsilon\\\hline
\rightarrow A\rightarrow&B&C&\\
B &C&C&A\\
C&C&C&
\end{array}
\]
dont l'\( \varepsilon\) -libéré est l'AEF
\[
\begin{array}{c|cc}
&a&b\\\hline
\rightarrow A\rightarrow &B&C\\
B\rightarrow &B, C&C\\
C&C&C
\end{array}
\]
dont l'automate déterministe est
\[
\begin{array}{c|cc}
&a&b\\\hline
\rightarrow \{A\}\rightarrow &\{B\}&\{C\}\\
\{B\}\rightarrow &\{B, C\}&\{C\}\\
\{C\}&\{C\}&\{C\}\\
\{B, C\}\rightarrow&\{B, C\}&\{C\}\\
\end{array}
\]
dont, pour y voir plus claire, nous pouvons renommer les états
\[
\begin{array}{c|cc}
&a&b\\\hline
\rightarrow U\rightarrow &V&W\\
V\rightarrow &X&W\\
W&W&W\\
X\rightarrow&X&W\\
\end{array}
\]
Proposition
Soit \( \A\) un automate.
\[L\left((\A^*)_\varepsilon\right)=L(\A^*)=L(\A)^*\]
Démonstration
C'est une conséquence triviale de la définition
Exercice
Pour chacun des automates suivants déterminer l'ADEF représentant l'automate étoile.
- \( \begin{array}{c|cc}
&a&b\\\hline
\rightarrow A\rightarrow &A&B\\
B &B&B
\end{array}\)
- \( \begin{array}{c|cc}
&a&b\\\hline
\rightarrow A&A&B\\
B\rightarrow &B&B
\end{array}\)
- \( \begin{array}{c|cc}
&a&b\\\hline
\rightarrow A&B&A\\
B\rightarrow &B&A
\end{array}\)
- \( \begin{array}{c|cc}
&a&b\\\hline
\rightarrow A&C&B\\
B &B&B\\
C\rightarrow &C&B
\end{array}\)