Automate fini déterministe

Un alphabet est, dans ce contexte, tout ensemble ${\displaystyle \Sigma }$ fini, non vide. Les éléments de ${\displaystyle \Sigma }$ sont appelés lettres.

Un mot est une suite finie d'éléments de ${\displaystyle \Sigma }$; la longueur d'un mot est le nombre d'éléments qui le composent. Un mot est noté par la juxtaposition de ses lettres. Ainsi, on écrit « oui » plutôt que « (o,u,i) ». Le mot vide, noté souvent ${\displaystyle \varepsilon }$, est l'unique mot de longueur zéro, composé d'aucune lettre. L'ensemble des mots sur ${\displaystyle \Sigma }$ est noté ${\displaystyle \Sigma ^{*}}$.

La concaténation de deux mots, notée ${\displaystyle \cdot }$ ou plus simplement par juxtaposition, est définie pour deux mots ${\displaystyle u=a_{1}\cdots a_{n}}$ et ${\displaystyle v=b_{1}\cdots b_{n}}$par ${\displaystyle uv=a_{1}\cdots a_{n}b_{1}\cdots b_{n}}$. On a ${\displaystyle u\varepsilon =\varepsilon u=u}$, la concaténation est associative : ${\displaystyle u(vw)=(uv)w}$, par conséquent ${\displaystyle (\Sigma ^{*},\cdot )}$ est un monoïde.

Un automate fini est un quintuplet ${\displaystyle {\mathcal {A}}=\langle \Sigma ,Q,R,I,F\rangle }$, où :

• ${\displaystyle \Sigma }$ est un alphabet,
• ${\displaystyle Q}$ est un ensemble fini, appelé ensemble des états,
• ${\displaystyle R}$ est une partie de ${\displaystyle Q\times \Sigma \times Q}$ appelée ensemble des transitions,
• ${\displaystyle I}$ est une partie de ${\displaystyle Q}$ appelée ensemble des états initiaux,
• ${\displaystyle F}$ est une partie de ${\displaystyle Q}$ appelée ensemble des états finaux.

Un automate est déterministe si, d'une part, il a un et un seul état initial et si, d'autre part, la relation ${\displaystyle R}$ est fonctionnelle au sens suivant :

si ${\displaystyle (p,a,q)\in R}$ et ${\displaystyle (p,a,q')\in R}$, alors ${\displaystyle q=q'}$.

S'il en est ainsi, on définit une fonction, appelée fonction de transition et notée traditionnellement ${\displaystyle \delta }$, par :

${\displaystyle \delta (p,a)=q}$ si ${\displaystyle (p,a,q)\in R}$.

C'est une fonction partielle ; son domaine de définition est l'ensemble des couples ${\displaystyle (p,a)\in Q\times \Sigma }$ tel qu'il existe ${\displaystyle q\in Q}$ avec ${\displaystyle (p,a,q)\in R}$. Dans les manuels, on rencontre aussi la définition suivante d'un automate fini déterministe qui est directe et n’est pas dérivée d'une définition plus générale :

Un automate fini déterministe est un quintuplet ${\displaystyle {\mathcal {A}}=\langle \Sigma ,Q,\delta ,q_{0},F\rangle }$, où :

• ${\displaystyle \Sigma }$ est un alphabet,
• ${\displaystyle Q}$ est un ensemble fini, appelé ensemble d'états,
• ${\displaystyle \delta }$ est une fonction (partielle) de ${\displaystyle Q\times \Sigma }$ dans ${\displaystyle Q}$ appelée fonction de transitions,
• ${\displaystyle q_{0}}$ est un élément de ${\displaystyle Q}$ appelé état initial,
• ${\displaystyle F}$ est une partie de ${\displaystyle Q}$ appelée ensemble des états finaux.

La fonction de transition ${\displaystyle \delta }$ est étendue en une application (partielle) ${\displaystyle Q\times \Sigma ^{*}\to Q}$ en posant

• ${\displaystyle \delta (q,\varepsilon )=q}$ pour tout état ${\displaystyle q}$. Ici ${\displaystyle \varepsilon }$ dénote le mot vide.
• ${\displaystyle \delta (q,wa)=\delta (\delta (q,w),a)}$ pour tout état ${\displaystyle q}$, tout mot ${\displaystyle w}$ et toute lettre ${\displaystyle a}$.

On rencontre — notamment dans la littérature francophone — une notation élégante introduite pas Samuel Eilenberg dans son traité[1] : la fonction de transition est notée par un simple point ${\displaystyle \cdot }$. Ainsi, au lieu d'écrire ${\displaystyle \delta (q,w)}$, on écrit ${\displaystyle q\cdot w}$. On a alors les formules :

• ${\displaystyle q\cdot \varepsilon =q}$;
• ${\displaystyle q\cdot wa=(q\cdot w)\cdot a}$.

Plus généralement, on a la formule

• ${\displaystyle q\cdot uv=(q\cdot u)\cdot v}$

pour des mots ${\displaystyle u}$ et ${\displaystyle v}$ qui se démontre traditionnellement par récurrence sur la longueur du mont ${\displaystyle v}$; le cas où ${\displaystyle v}$ est le mot vide ou est une lettre est vérifié par les formules précédent, et plus généralement, si ${\displaystyle v=za}$ pour une lettre ${\displaystyle a}$, on a

• ${\displaystyle q\cdot uv=q\cdot uza=(q\cdot uz)\cdot a=((q\cdot u)\cdot z)\cdot a=(q\cdot u)\cdot za=(q\cdot u)\cdot v}$.

Algébriquement, la dernière formule exprime que le monoïde libre ${\displaystyle \Sigma ^{*}}$ opère à droite sur l'ensemble d'états de l’automate.

Un automate fini, déterministe ou non, est représenté par un graphe dont les sommets sont les états, et les arcs sont les transitions. C'est donc un graphe orienté, étiqueté aux arcs par des lettres de l’alphabet. Une symbolique spéciale distingue les états initiaux et terminaux : un état initial est marqué par une flèche entrante, un état terminal par une flèche sortante ou par un double cercle.

Une transition ${\displaystyle (p,a,q)\in R}$ est souvent écrite sous la forme ${\displaystyle p{\overset {a}{\longrightarrow }}q}$, empruntée à la représentation graphique. Un chemin est une suite de flèches consécutives, notée

${\displaystyle q_{0}{\xrightarrow {a_{1}}}q_{1}{\xrightarrow {a_{2}}}q_{2}\rightarrow \cdots {\xrightarrow {a_{n}}}q_{n}}$.

Sa longueur est le nombre ${\displaystyle n}$ de ses transitions, son étiquette (ou trace) est le mot ${\displaystyle a_{1}a_{2}\cdots a_{n}}$ formé des étiquettes de ses arcs.

On dit qu'un chemin est réussi lorsque ${\displaystyle q_{0}\in I}$ et ${\displaystyle q_{k}\in F}$. Un mot est reconnu lorsqu'il est l'étiquette d'un chemin réussi. Le langage accepté ou reconnu par l’automate est l’ensemble des mots qu'il reconnaît.

Dans le cas d'un automate fini déterministe, il n'y a, pour un mot ${\displaystyle w}$ et pour un état ${\displaystyle q}$, au plus un chemin partant de ${\displaystyle q}$ et d'étiquette ${\displaystyle w}$; s'il existe, ce chemin a pour sommet d'arrivée ${\displaystyle \delta (q,w)}$. Dire qu'un mot ${\displaystyle w}$ est reconnu s'exprime donc par le fait que ${\displaystyle \delta (q_{0},w)}$ est un état final lorsque ${\displaystyle q_{0}}$ est l'état initial. En d'autres termes, le langage accepté ou reconnu par l’automate ${\displaystyle {\mathcal {A}}}$ est

${\displaystyle L({\mathcal {A}})=\{w\in \Sigma ^{*}\mid \delta (q_{0},w)\in F\}}$.

Avec la notation par point, cette expression s'écrit

${\displaystyle L({\mathcal {A}})=\{w\in \Sigma ^{*}\mid q_{0}\cdot w\in F\}}$.

Si on utilise la notation par point, on omet le symbole ${\displaystyle \delta }$ dans la définition de l’automate.

Automate fini reconnaissant les mots commençant par ab.

L'automate ci-contre est composé de trois états; l'état 1 est le seul état initial, distingué par une flèche entrante, l'état 3 est le seul état terminal, distingué par une flèche sortante. C'est un automate déterministe. Il reconnaît les mots, sur deux lettres a et b, qui commencent par ab. La fonction de transition est donnée par sa table de transitions. L'absence de flèche est représentée par un tiret : la présence d'un tiret montre que la fonction de transition est partielle.

La complexité d’un langage rationnel L peut se mesurer de diverses façons ; dans le cadre des automates finis déterministes, il est nature de la définir comme le nombre d’états de l’automate déterministe complet minimal reconnaissant ce langage. Par le théorème de Myhill-Nerode, c'est aussi le nombre de résiduels ou quotients gauches du langage. On note ce nombre ${\displaystyle \kappa (L)}$ avec Brzozowski[2].

La complexité d'une opération binaire ${\displaystyle \odot }$ sur des langages L et M est notée ${\displaystyle \kappa (L\odot M)}$. C'est une fonction de ${\displaystyle \kappa (L)}$ et de ${\displaystyle \kappa (M)}$. Les opérations booléennes et leurs composées à considérer sont notamment

• complémentation ${\displaystyle {\overline {L}}}$
• union ${\displaystyle L\cup M}$
• intersection ${\displaystyle L\cap M}$
• différence symétrique ${\displaystyle L\oplus M}$
• différence ${\displaystyle L\setminus M}$

On a par exemple ${\displaystyle \kappa ({\overline {L}})=\kappa (L)}$ puisque les automates minimaux ne diffèrent que par les états terminaux dont les ensembles sont complémentaire. La complexité d’autres opérations peut s’en déduire, par exemple :

${\displaystyle \kappa ({\overline {L}}\cup M)=\kappa ({\overline {{\bar {L}}\cup M}})=\kappa (L\cap {\overline {M}})=\kappa (L\setminus M)}$.

Quand on évalue la complexité des opérations, il faut préciser si les langages sont donnés sur le même alphabet ou non. Soient L et M deux langages rationnels de complexité ${\displaystyle \kappa (L)=m}$ et ${\displaystyle \kappa (M)=n}$ respectivement, pas nécessairement sur le même alphabet. Les résultats sont les suivants :

• La complexité de l’union et de la différence symétrique de L et M est au plus ${\displaystyle (m+1)(n+1)}$ La complexité de l’union de langages L et M sur le même alphabet est au plus mn.
• La complexité de la différence est au plus ${\displaystyle (m+1)n}$.
• La complexité de l’intersection est au plus ${\displaystyle mn}$.
• La complexité du produit LM est au plus ${\displaystyle m2^{n}-2^{n-1}}$.

Toutes ces bornes peuvent être atteintes. Pour illustrer l'importance de l'alphabet, on considère les langages ${\displaystyle L=a^{*}}$ et ${\displaystyle M=b^{*}}$ formés des mots sur une seule lettre ${\displaystyle a}$ respectivement ${\displaystyle b}$, avec ${\displaystyle a\neq b}$. Chacun des deux langages est reconnu par un automate à un seul état. La réunion ${\displaystyle a^{*}\cup b^{*}}$ est de complexité 4=(1+1)(1+1). Si les langages ${\displaystyle L=a^{*}}$ et ${\displaystyle M=b^{*}}$ sont considérés comme étant l'un et l'autre sur l'alphabet ${\displaystyle \{a,b\}}$, leurs automates minimaux ont chacun 2 états et l'automate de leur union a bien ${\displaystyle 4=2\cdot 2}$ états.

Les algorithmes pour le calcul de l'automate reconnaissant le produit ou l’étoile d'un langage décrits pour les automates non déterministes sont bien entendu applicables aussi quand on part d'un automate déterministe, mais le résultat est un automate non déterministe, et même avec des ε-transitions. Autant le non déterminisme ne s'élimine que dans une deuxième étape, autant on peut, avec un peu de soin, éviter l'introduction des ε-transitions dont l'élimination ultérieure constitue une phase supplémentaire dans la construction[3].

Automate pour le produit

Soient ${\displaystyle {\mathcal {A}}=\langle \Sigma ,Q,q_{0},F\rangle }$ et ${\displaystyle {\mathcal {B}}=\langle \Sigma ,P,p_{0},T\rangle }$ deux automates finis déterministes reconnaissant des langages ${\displaystyle L}$ et ${\displaystyle M}$ respectivement. Un automate non déterministe ${\displaystyle {\mathcal {C}}}$ reconnaissant le langage produit ${\displaystyle LM}$ est défini comme suit : l'ensemble de ses états est ${\displaystyle Q\cup P}$ (on suppose ces deux ensembles disjoints), l'état initial est ${\displaystyle q_{0}}$ (l'état initial de ${\displaystyle {\mathcal {A}}}$, l'ensemble des états terminaux est ${\displaystyle T}$ (états terminaux de ${\displaystyle {\mathcal {B}}}$). Les transitions sont celles définies par les fonctions de transitions de ${\displaystyle {\mathcal {A}}}$ et ${\displaystyle {\mathcal {B}}}$, avec en plus des transitions ${\displaystyle (q,a,p_{0})}$ pour toute paire ${\displaystyle (q,a)}$ formée d'un état de ${\displaystyle {\mathcal {A}}}$ et d'une lettre telle que ${\displaystyle q\cdot a\in F}$. Ainsi, chaque fois que l’automate ${\displaystyle {\mathcal {A}}}$ arrive dans un état qui peut déboucher sur in de ses états finaux, la transition ajoutée permet aussi d'anticiper le début d'un calcul dans l’automate ${\displaystyle {\mathcal {B}}}$.

Automate pour l'étoile

La construction est analogue. Partant d'un automate ${\displaystyle {\mathcal {A}}=\langle \Sigma ,Q,q_{0},F\rangle }$, on construit un automate

${\displaystyle {\mathcal {B}}=\langle \Sigma ,Q\cup p_{0},p_{0},F\cup p_{0}\rangle }$,

où ${\displaystyle p_{0}}$ est un nouvel état qui est son état initial et aussi un état final. La fonction de transition de ${\displaystyle {\mathcal {A}}}$ est étendue à ${\displaystyle p_{0}}$ par

${\displaystyle p_{0}\cdot a=q_{0}\cdot a}$ pour toute lettre ${\displaystyle a}$;

de plus, on ajoute les transitions ${\displaystyle (q,a,q_{0})}$ pour quand ${\displaystyle q\cdot a\in F}$, et la transition ${\displaystyle (p_{0},a,q_{0})}$ si ${\displaystyle q_{0}\cdot a\in F}$.

Deux automates finis déterministes sont équivalents s'ils reconnaissent le même langage. C'est un résultat remarquable de la théorie qu'il existe, pour tout automate fini, un seul automate fini déterministe minimal (c'est-à-dire ayant un nombre minimal d'état) qui est équivalent à l'automate donné. De plus, cet automate, appelé automate minimal, possède une description algébrique simple et élégante. Par ailleurs, l'automate se calcule efficacement par l'algorithme de Moore ou l'algorithme de Hopcroft. L'unicité de l'automate ayant un nombre minimal d'état n'est plus vraie pour les automates non déterministes.

• Automate fini
• Automate fini non déterministe
• Automate fini inambigu
• Automate à pile
• Automate d'arbres
• Théorème de Kleene

Ouvrages

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5)
  Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press 2009, (ISBN 9780521844253)
• Patrice Séébold, Théorie des automates : Méthodes et exercices corrigés, Vuibert, 1999, 198 p. (ISBN 978-2-7117-8630-5)
• Jean-Éric Pin, « Automates finis », dans Jacky Akoka et Isabelle Comyn-Wattiau (éditeurs), Encyclopédie de l'informatique et des systèmes d'information, Paris, Vuibert, 2006, xxxv+1941 (ISBN 978-2-7117-4846-4), p. 966-976.
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2007, 3^e éd. (ISBN 978-0-32146225-1)
• Samuel Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, 1974 (ISBN 978-0-12-234001-7)

Cours

• Luc Maranget, « Chapitre 7 Les automates », Notes de cours à l’École polytechnique.
• Jean-Marc Fédou, « 8. Automates finis », Université de Nice.
• Sylvain Lombardi, « Automates, Notions de base », Université Marne-la-Vallée.
• Élise Bonzon, « Théorie de Langages - Automates finis », Université Paris Descartes.
• Benjamin Monmège et Sylvain Schmitz, « Automates et langages », Préparation à l’agrégation de mathématiques 2011–2012, LSV, ENS Cachan & CNRS.
• Abdelmajid Dergham[6],Université Mohammed Premier Oujda.