Définition
Soient \( \A\) un AEF\( \varepsilon\) , \( \sigma\in\Sigma_\A^*\) tel que \( \norm{\sigma}=n\) . On dira que \( \sigma\) est
accepté par \( \A\) si il existe une suite \( e_0, e_1, \dots, e_n\) de \( E_\A\) tel que
- \( e_0\in I_\A\) ,
- \( e_n\in F_\A\) ,
- \( \forall k\in [\![1,n]\!], \ \tau_\A(e_{k-1},\sigma_k)=e_{k}\)
Autrement dit : un mot de longueur \( n\) est accepté par un automate s'il existe un chaine de longueur \( n-1\) dans le graphe représentant l'automate ayant un état initial pour origine et un état final pour aboutissement.
Exemple
\[\xymatrix@C=2cm{
\ar[d]&\\
p\ar@/^2pc/[r]^0\ar@(ld,lu)[]^1\ar[d]
&i\ar@/^2pc/[l]^0\ar@(rd,ru)[]_1\\
&
}
\]
Les mots \( \varepsilon\) , \( 001\) , \( 100\) , \( 1100\) , \( 010\) sont acceptés par l'automate ci-contre.
Définition
Le langage d'un AEF\( \varepsilon\) \( \A\) est l'ensemble des mots acceptés.
\[L(\A)=\left\{\sigma\in\Sigma_\A^*\Big| \sigma \text{ est accepté par }\A\right\}\]
Exemple
\[\xymatrix@C=2cm{
\ar[d]&\\
p\ar@/^2pc/[r]^0\ar@(ld,lu)[]^1\ar[d]
&i\ar@/^2pc/[l]^0\ar@(rd,ru)[]_1\\
&
}
\]
Les mots reconnus par cet automate sont tous les mots de \( \{0,1\}\) possédant un nombre paire de \( 0\) .
Définition
Soient \( \Sigma\) un alphabet et \( L\subset \Sigma^*\) un langage. On dira que \( L\) est un langage d'états finis, s'il existe un ADEF \( \A\) tel que \( \Sigma=\Sigma_\A\) et \( L(\A)=L\) . On dit que l'automate \( \A\) reconnait le langage \( L\) .
Exemple
Considérons l'alphabet \( \Sigma=\{0,1,2,3,4,5,6,7,8,9\}\) et le langage \( L=\N\) des nombres. Il s'agit d'un langage d'états finis. En effet les nombres (ne commençant pas par \( 0\) sauf \( 0\) lui même) sont reconnus par l'A(D)EF suivant :
\[
\xymatrix@C=3cm{
&\ar[d]&\\
&\varnothing\ar[rd]^0\ar[ld]_{1,\dots,9}&\\
Vrai\ar[d]\ar@(ld,lu)[]^\Sigma&Faux\ar@(ld,rd)[]_\Sigma&0\ar[d]\ar[l]^\Sigma\\
&&\\
}
\]
Théorème [Rabin-Scott]
Soit \( \A\) un AEF.
\[L(\A)=L(\A_{det})\]
Démonstration
Admise
Il est parfois plus naturel de construire une AEF qui traduit un langage puis de le déterminer (et le compléter) pour pouvoir le programmer.
Exemple
Considérons l'AEF qui reconnait les mots de l'alphabet \( \Sigma=\{a,b\}\) qui se termine par \( bab\) :
\[
\xymatrix{
\ar[r]&
0\ar[r]^b\ar@(lu,ru)[]^a\ar@(ld,rd)[]_b&
1\ar[r]^a&
2\ar[r]^b&
3\ar[r]
&}
\]
Le déterminé (complété) de cet AEF est
\[
\xymatrix{
\ar[r]&
A\ar[r]^b\ar@(lu,ru)[]_a&
B\ar[r]^a\ar@(lu,ru)[]_b&
C\ar@/^1pc/[r]^b\ar@/_2pc/[ll]_a&
D\ar[r]\ar@/^2pc/[ll]^b\ar@/^1pc/[l]_a&
&}
\]
Théorème
Soit \( \A\) un AEF\( \varepsilon\) .
\[L(\A)=L(\A_\varepsilon)\]
Démonstration
Admise.
Exercice
Décrire un automate déterministe et complet permettant de reconnaitre les langages suivants.
- Les mots finissant par \( bab\) sur l'alphabet \( \Sigma=\{a,b\}\) .
- Les mots commençant par \( aba\) sur l'alphabet \( \Sigma=\{a,b\}\) .
- Les mots ne contenant pas de \( 00\) sur l'alphabet \( \Sigma=\{0,1\}\) .
- Les nombres entiers (\( \N\) ) sur \( \Sigma=\{0,1,2,3,4,5,6,7,8,9\}\) .
- Les nombres entiers paires (\( 2\N\) ) sur \( \Sigma=\{0,1,2,3,4,5,6,7,8,9\}\) .
- Les nombres entiers divisible par 3 (\( 3\N\) ) sur \( \Sigma=\{0,1,2,3,4,5,6,7,8,9\}\) .
- Les entiers relatifs (\( \Z\) ) sur l'alphabet \( \Sigma=\{0,1,2,3,4,5,6,7,8,9,-\}\) .
- Les expressions mathématiques correctes sur l'alphabet \( \Sigma=\{0,1,2,3,4,5,6,7,8,9,+,-\}\) .