Théorème [Lemme d'Arden]
Soient \( A\) et \( B\) deux langages sur un alphabet \( \Sigma\) .
- \( (i)\)
- Une solution de l'équation \( L=AL\cup B\) est \( L=A^*B\) .
- \( (ii)\)
- Si \( \varepsilon\not\in A\) , \( L=A^*B\) est l'unique solution de l'équation \( L=AL\cup L\)
Démonstration
Admise
Ce théorème est très puissant et va permettre de déterminer le langage reconnu par un automate.
Définition
Soient \( i\) et \( j\) des états d'un ADEF \( \A\) et \( L\) un langage sur \( \Sigma_\A\) . On note
- \( \Sigma_{i, j}\)
- l'ensemble des lettres de l'alphabet qui permettent de passer de l'état \( i\) à l'état \( j\) .
\[\Sigma_{i, j}=\left\{x\in \Sigma\Big| \tau_\A(i, x)=j\right\}\]
- \( \A_i\)
- l'automate identique à l'automate \( \A\) où l'état initial a été remplacé par \( i\) .
\[\sigma_{\A_i}=\Sigma_\A, \
E_{\A_i}=E_\A, \
I_{\A_i}=\{i\}, \
F_{\A_i}=F_{\A}, \
\tau_{\A_i}=\tau_\A\]
Exemple
Considérons l'automate
\[
\xymatrix{
\ar[r]&A\ar[r]^a\ar@(lu, ru)[]^b&B\ar[r]^a\ar@(lu, ru)[]^b&C\ar[r]\ar@/^1pc/[ll]^a\ar@(lu, ru)[]^b\ar[r]&
}
\]
On a
\( \Sigma_{A, A}=\{b\}\) , \( \Sigma_{A, B}=\{a\}\) , \( \Sigma_{A, C}=\varnothing\) .
De même \( \A_A=\A\) et \( \A_C\) est l'automate
\[
\xymatrix{
&A\ar[r]^a\ar@(lu, ru)[]^b&B\ar[r]^a\ar@(lu, ru)[]^b&C\ar[r]\ar@/^1pc/[ll]^a\ar@(lu, ru)[]^b\ar[r]&\\
&&&\ar[u]&
}
\]
Proposition
Soit \( \A\) un automate.
\[
\begin{array}{lrl}
\forall i \in E_\A-F_\A & L(\A_i) = & \dpl{\bigcup_{j\in E_\A} \Sigma_{i, j}L(\A_j)}\\
\forall i \in F_\A & L(\A_i) = & \dpl{\{\varepsilon\}\cup\bigcup_{j\in E_\A} \Sigma_{i, j}L(\A_j)}
\end{array}
\]
Démonstration
Notons \( L_i=L(\A_i)\) .
On observe pour commencer que si \( \varepsilon\) est un mot reconnu alors l'état initial est un état final. En particulier \( \varepsilon\in L_f\) si \( f\) est un état final, la réciproque est trivialement vrai. Ainsi pour démontrer les deux cas de la proposition, il suffit de montrer que \( L_i-\{\varepsilon\}=\dpl{\bigcup_{j\in E_\A} \Sigma_{i, j}L_j}\) .
- \( \dpl{\bigcup_{j\in E_\A} \Sigma_{i, j}L_j}\subseteq L_i-\{\varepsilon\}\) .
- Si \( a\in \Sigma_{i, j}\) et \( m\in L_j\) alors \( am\in L_i\) donc \( \Sigma_{i, j}L_j\subset L_j\) et à fortiori \( \dpl{\bigcup_{j\in E_\A} \Sigma_{i, j}L_j}\subseteq L_i-\{\varepsilon\}\) .
- \( \dpl{L_i-\{\varepsilon\}\subseteq\bigcup_{j\in E_\A} \Sigma_{i, j}L_j}\) .
- Soit \( m\in L_i-\{\varepsilon\}\) et \( a\in \Sigma_\A\) la première lettre de \( m\) : \( m=am'\) . Posons \( j=\tau_\A(i, a)\) alors \( m'\in L_j\) ainsi \( am=\Sigma_{i, j}L_j\) ce qui prouve l'inclusion.
Exemple
Reprenons l'automate précédent. Notons \( L_{X}=L(\A_X)\) .
\[L_A = \Sigma_{A, A}L_{A}\cup\Sigma_{A, B}L_B\cup\Sigma_{A, C}L_C\]
Nous avons \( \Sigma_{A, A}=\{b\}\) , \( \Sigma_{A, B}=\{a\}\) et \( \Sigma_{A, C}=\varnothing\) . Sachant que pour tout langage \( L\) on a \( \varnothing L = \varnothing\) , l'égalité précédente se simplifie en
\[L_A = \{b\}L_{A}\cup\{a\}L_B\]
Le lemme d'Arden permet alors de trouver \( L_A\) :
\( L_A=\{b\}^*\{a\}L_B\)
De la même manière, on a \( L_B=\{b\}L_B\cup\{a\}L_C\) qui permet, par le lemme d'Arden, d'obtenir \( L_B=\{b\}^*\{a\}L_C\) ce qui donne en jumelant avec l'égalité précédente :
\[L_A=\{b\}^*\{a\}\left(\{b\}^*\{a\}L_C\right)=\left(\{b\}^*\{a\}\right)^2L_C\]
Enfin, puisque \( C\) est final, on a \(
L_{C}=\{\varepsilon\}\cup\{b\}L_C\cup\{a\}L_A
\) ce qui donne par le lemme d'Arden
\begin{eqnarray*}
L_C&=&\{b\}^*\left(\{\varepsilon\}\cup\{a\}L_A\right)\\
&=&\{b\}^*\{\varepsilon\}\cup\{b\}^*\{a\}L_A\\
&=&\{b\}^*\cup\{b\}^*\{a\}L_A
\end{eqnarray*}
En jumelant nos deux dernières égalités nous arrivons a
\begin{eqnarray*}
L_A&=&\left(\{b\}^*\{a\}\right)^2L_C\\
&=&\left(\{b\}^*\{a\}\right)^2\left(\{b\}^*\cup\{b\}^*\{a\}L_A\right)\\
&=&
\left(\left(\{b\}^*\{a\}\right)^2\{b\}^*\right)
\cup
\left(\left(\{b\}^*\{a\}\right)^2\{b\}^*\{a\}L_A\right)\\
&=&
\left(\left(\{b\}^*\{a\}\right)^2\{b\}^*\right)
\cup
\left(\left(\{b\}^*\{a\}\right)^3L_A\right)\\
\end{eqnarray*}
Encore un petit coup de lemme d'Arden pour pouvoir conclure (puisque \( L=L_A\) ) :
\[
L = \left(\left(\{b\}^*\{a\}\right)^3\right)^*\left(\left(\{b\}^*\{a\}\right)^2\{b\}^*\right)
\]
De plus, il est évident que la REGEX associée est \( \left(\left({b}^*{a}\right)^3\right)^*\left(\left({b}^*{a}\right)^2{b}^*\right)\) .
Exercice
Pour chacun des automates suivants, calculer une REGEX reconnaissant le langage de l'automate.
- \( \begin{array}{c|*{3}{c}} & \alpha & \beta \\ \hline A & B& C \\ B \rightarrow & C & C \\ \rightarrow C & B & C \\ \end{array}\)
- \( \begin{array}{c|*{3}{c}} & 0 & 1 \\ \hline A & B & A \\ \rightarrow B & A & C \\ C \rightarrow & C & A \\ \end{array}\)
- \( \begin{array}{c|*{3}{c}} & u & v \\ \hline \rightarrow A & A & A \\ B \rightarrow & B & A \\ C & B & A \\ \end{array}\)
- \( \begin{array}{c|*{3}{c}} & u & v \\ \hline \rightarrow A & C & A \\ B \rightarrow & B & A \\ C & B & A \\ \end{array}\)
- \( \begin{array}{c|*{3}{c}} & u & v \\ \hline \rightarrow A & C & A \\ B \rightarrow & B & A \\ C & B & A \\ \end{array}\)
- \( \begin{array}{c|*{3}{c}} & x & y \\ \hline A & C & A, B, C \\ \rightarrow B & B & A, C \\ C \rightarrow & B & B, C \\ \end{array}\)
