Cours précédent
Cours suivant
Mots et langages acceptés part un automate fini
Un calcul (ou un run) d’un AF sur un mot est un chemin de transitions consécutives qui part de l’état initial de l’AF.
Un calcul acceptant est un calcul qui termine dans un état final.
Un mot accepté est un mot pour lequel il existe au moins un calcul acceptant sur l’AF de ce mot.
Un langage reconnue par un AF est l’ensemble des mots reconnus, noté L(A).
Il existe des algorithmes qui permettent d’exprimer sous la forme d’une expression rationnelle le langage accepté par un automate fini.
Automates finis et matrices d’adjacence.
On peut representer un AF par la matrice d’adjacence M du graphe orienté associé.
\((M^k)_{ij}\) correspond aux mots de longueur k reconnu par l’AF quand on va de l’état i à l’état j.
Automates complets
Un automate fini \(C = (A, Q, I, F, \delta)\) est un automate complet si pour chaque état \(q\in Q\) et pour chaque lettre \(a \in A\), il existe au moins une transition étiqueté par \(a\) sortant de l’état \(q\).
Exemple :
De l’état 1 il n’y a pas de transition avec b, de même pour l’état 2 avec a. Donc l’automate n’est pas complet.
Construction d’un automate complet
Soit \(C=(A, Q, I, F, \delta)\) un automate fini et \(D=(A, Q\cup\{q\}, I, F, \delta')\) où \(q\) est un nouvel état, \(\delta' = \delta\cup\{(p, \alpha, q)\setminus p\in Q, \alpha\in A,\) il n’y a pas de transition de la forme \((p,\alpha, p')\in \delta\} \cup \{(q,\alpha, q)\ \forall \alpha \in A\}\).
Alors, l’automate D, appelé le complété de C, est un automate complet et L(C) = L(D)
Preuve : Les nouvelles transitions n’ont pas d’impact sur les mots reconnus.
Exemple :
Graphe non complet C :
L(C) = ab*
Graphe complet D :
L(D) = ab* = L(C)
Automates déterministes
Un automate fini \(C=(A,Q,I,F,\delta)\) est déterministe si :
- Il y a un seul état initial
- Pour tout état \(q\in Q\) et pour toute lettre \(\alpha\in A\), il y a au plus une transition étiqueté \(\alpha\) qui sort de l’état \(q\).
Exemple :
Cet automate n’est pas déterministe car il y a deux transitions étiquetés b qui sortent de 1.
Cet automate est déterministe.
Complémentaire
Soit \(C = (A, Q, I, F, \delta)\) un automate complet et déterministe.
Soit \(D = (A, Q, I, Q\setminus F, \delta)\) (on rend les états finaux non-finaux et vice-versa).
Alors l’automate fini D reconnait le langage complémentaire de celui reconnu par C.
L(D) = A*\L(C)
Le complémentaire (ou complément) d’un ensemble \(L\subseteq A^*\) est l’ensemble A*\L.
Retour
Cours précédent
Cours suivant