---

We need Your Support. Make a Donation now! or

---

Chapitre�7��Les automates

• Pourquoi �tudier les automates
• Rappel : alphabets, mots, langages et probl�mes
• Automates finis d�terministes
• Automates finis non-d�terministes
• Automates finis et expressions r�guli�res
• Un peu de Java

7.1��Pourquoi �tudier les automates

Ce chapitre est une tr�s succincte introduction � la th�orie des automates que vous aurez l’occasion de voir de fa�on d�taill�e si vous choisissez un cursus d’informatique. Ce chapitre est, par nature, un peu plus “th�orique” et un peu moins algorithmique que les pr�c�dents.

Les automates sont des objets math�matiques, tr�s utilis�s en informatique, qui permettent de mod�liser un grand nombre de syst�mes (informatiques). L’�tude des automates a commenc� vers la fin des ann�es cinquante. Elle se base sur de nombreuses techniques (topologie, th�orie des graphes, logique, alg�bre, etc.). De fa�on tr�s informelle, un automate est un ensemble “d’�tats du syst�me”, reli�s entre eux par des “transitions” qui sont marqu�es par des symboles. �tant donn� un “mot” fourni en entr�e, l’automate lit les symboles du mot un par un et va d’�tat en �tat selon les transitions. Le mot lu est soit accept� par l’automate soit rejet�.

Avant de donner une d�finition plus formelle des concepts d�crits ci-dessus, citons quelques exemples classiques d’utilisation d’automates :

• V�rification d’un circuit �lectronique
• Recherche d’occurrence dans un texte (moteur de recherches sur le web, etc.)
• V�rification de protocoles de communication
• Compression de donn�es
• Compilation
• Biologie (g�nomique)

En dehors de ces utilisations “pratiques” des automates, notons qu’ils sont aussi utilis�s pour mod�liser les ordinateurs et pour comprendre ce qu’un ordinateur peut faire (d�cidabilit�) et ce qu’il sait faire efficacement (complexit�). C’est donc une notion fondamentale de l’informatique.

7.2��Rappel : alphabets, mots, langages et probl�mes

Nous reprenons ici les notations du chapitre�6. L’alphabet Σ est un ensemble de caract�res (ou symboles). un mot est une suite finie de caract�res. L’ensemble des mots sur Σ est not� Σ^*. Un langage est un sous-ensemble de Σ^*, c’est-�-dire un ensemble particulier de mots. Parmi les mots de Σ^* on distingue le mot vide not� є. Le mot vide est l’unique mot de longueur z�ro.

7.3��Automates finis d�terministes

Un automate fini d�terministe est un quintupl� (Q, Σ, δ, q₀, F) constitu� des �l�ments suivants

• un alphabet fini (Σ)
• un ensemble fini d’�tats (Q)
• une fonction de transition (δ : Q * Σ → Q)
• un �tat de d�part (q₀ ∈ Q)
• un ensemble d’�tats finaux (ou acceptant) F ⊆ Q

7.3.1��Fonctionnement d’un automate fini d�terministe

L’automate prend en entr�e un mot et l’accepte ou la rejette. On dit aussi qu’il le reconna�t ou ne le reconna�t pas. Le langage associ� � un automate est constitu� de l’ensemble des mots qu’il reconna�t. Voici comment l’automate proc�de pour d�cider si un mot appartient � son langage.

• Le processus commence � l’�tat de d�part q₀
• Les symboles du mot sont lus les uns apr�s les les autres.
• � la lecture de chaque symbole, on emploie la fonction de transition δ pour se d�placer vers le prochain �tat (en utilisant l’�tat actuel et le caract�re qui vient d’�tre lu).
• le mot est reconnu si et seulement si le dernier �tat (i.e., l’�tat correspondant � la lecture du dernier caract�re du mot) est un �tat de F.

De fa�on plus formelle, pour d�finir exactement le langage reconnu par un automate, nous introduisons la fonction de transition �tendue aux mots, δ. Elle se d�finit r�cursivement comme suit.

• A partir d’un �tat q en lisant le mot vide є on reste dans l’�tat q, i.e., ∀ q ∈ Q, δ(q, є) = q
• �tant donn� un mot c se terminant par a ∈ Σ (i.e., c = c′a avec c′ ∈ Σ ∪ {є}), et un �tat q de Q, δ(q, c) = δ(q, c′a) = δ(δ(q, c′), a)

Nous pouvons maintenant d�finir le langage L(A) accept� par un automate fini d�terministe A = (Q, Σ, δ, q₀, F).

7.3.2��Des repr�sentation “compactes” des automates

On peut associer � un automate une table de transition qui d�crit de mani�re extensive la fonction de transition δ :

• Une colonne correspond � un caract�re de l’alphabet.
• Une ligne correspond � un �tat de l’automate (l’�tat initial est pr�c�d� d’une fl�che “→”; l’�tat final d’une �toile “*”)

La valeur δ(q, a) pour q ∈ Q, a ∈ Σ correspond � l’�tat indiqu� � l’intersection de la ligne q et de la colonne a. Notons qu’� partir de cette table il est ais� de retrouver l’ensemble des �tats ainsi que l’alphabet et donc d’identifier exactement l’automate.

Pour repr�senter de fa�on tr�s intuitive un automate fini d�terministe (Q, Σ, δ, q₀, F), on peut utiliser un graphe de transition constitu� des �l�ments suivants :

• Un ensemble de sommets (chaque sommet repr�sente un �l�ment de Q).
• Un ensemble d’arcs entre les sommets valu�s par un symbole de σ (un arc entre les �tats q et q′ valu� par le symbole s signifie que δ(q, s) = q′).
• L’�tat initial q₀ est marqu� par une fl�che entrante.
• Les �tats finaux F sont entour�s d’une double ligne.

L’automate de l’exemple 7.1 est ainsi repr�sent� sur la figure 7.1.

---

Figure 7.1: Un automate fini d�terministe

---

Pour simplifier encore cette repr�sentation, un arc entre deux sommets q, q′ peut �tre valu� par plusieurs symboles s₁, ..., s_n s�par�s par des virgules. Cette derni�re convention signifie simplement que ∀ i ≤ n, δ(q, s_i) = q′ et elle permet d’�viter une multiplication d’arcs sur le graphe. La figure 7.2 illustre une telle simplification.

---

Figure 7.2: Deux repr�sentations �quivalentes du m�me automate fini

---

Exercice�7.2�� �crire la table de transition de l’automate suivant. Quel est le langage reconnu ?

Solution.

� □

Solution.

□

7.4��Automates finis non-d�terministes

Un automate fini non-d�terministe est un automate tel que dans un �tat donn�, il peut y avoir plusieurs transitions avec le m�me symbole. le fonctionnement d’un tel automate n’est donc pas totalement ��d�termin頻, car on ne sait pas quel �tat l’automate va choisir.

Les automates non-d�terministes permettent de mod�liser facilement des probl�mes complexes. Ils peuvent �tre convertis en des automates finis d�terministe. Ces derniers peuvent �tre exponentiellement plus grand que les automates non d�terministe dont ils sont issus.

Un automate fini non-d�terministe est un quintupl� : (Q, Σ, δ, q₀, F)

• un alphabet fini (Σ)

• un ensemble fini d’�tats (Q)

• une fonction de transition δ qui associe � tout �tat q ∈ Q et tout symbole s ∈ Σ un sous ensemble de Q not� δ(q, s).
• un �tat de d�part (q₀)
• un ensemble d’�tats finaux (ou acceptant) F

C’est la fonction de transition δ qui diff�re ici de celle utilis�e par les automates finis d�terministes. Remarquons que tout automate fini d�terministe est aussi un automate fini non-d�terministe.

Les repr�sentations compactes des automates finis d�terministes s’�tendent naturellement aux automates finis non-d�terministes. Une cellule de la table de transition contient un sous-ensemble d’�tats (�ventuellement vide).

7.4.1��Fonctionnement d’un automate fini non-d�terministe

Comme pour un automate fini d�terministe, l’automate prend en entr�e un mot et l’accepte ou le rejette. Le langage associ� est constitu� de l’ensemble des mots qu’il reconna�t.

Exemple�7.2�� Voici automate qui reconna�t les mots d�finis sur l’alphabet {a, b, c} qui commencent par a et qui finissent par c.

La table associ�e � cet automate est alors :

	a	b	c
→ q0	{q1}	∅	∅
q1	{q1}	{q1}	{q1, q2}
* q2	∅	∅	∅

Comme pour les automates d�terministes, nous nous introduisons la fonction de transition �tendue aux mots, δ. Elle se d�finit r�cursivement comme suit.

• A partir d’un �tat q en lisant le mot vide є (le mot vide ne contient aucun symbole et est toujours not� є), on reste dans l’�tat q, i.e., ∀ q ∈ Q, δ(q, є) = {q}
• �tant donn� un mot c se terminant par a ∈ Σ (i.e., c = c′a avec c′ ∈ Σ ∪ {є}), et un �tat q de Q,

  δ(q,�c)�=�δ(q,�c′a)� =

  ∪ p�∈�δ(q,�c′)

  �δ(p,�a)

Nous pouvons maintenant d�finir le langage L(A) accept� par un automate fini d�terministe A = (Q, Σ, δ, q₀, F).

Solution.

□

Solution.

□

Solution.

□

7.4.2��D�terminisation d’un automate fini non-d�terministe

Un automate fini d�terministe est aussi non-d�terministe. Donc tout langage reconnu par un automate fini d�terministe est reconnu par un automate fini non-d�terministe. Plus surprenant, la r�ciproque est aussi vraie (Th�or�me de Rabin-Scott).

Consid�rons un automate fini non-d�terministe A_n = (Q_n, Σ, δ_n, q₀, F_n) et construisons un automate fini d�terministe A_d = (Q_d, Σ, δ_d, {q₀}, F_d) qui reconna�t exactement le m�me langage.

• Les alphabets de A_n et de A_d sont identiques.
• Les �tats de d�part sont respectivement q₀ et le singleton {q₀}.
• Q_d est constitu� de tous les sous-ensembles de Q_n.
• F_d est l’ensemble des sous-ensembles de Q_n qui contiennent au moins un �l�ment de F_n.
• �tant donn� un sous ensemble S de Q_n et un symbole a ∈ Σ, on d�finit la fonction de transition δ_d(S,a) de la mani�re suivante

  δd(S,a)�=�

  ∪ q�∈�S

  �δn(q,�a).

Nous illustrons le th�or�me de Rabin-Scott sur quelques exemples.

Exemple�7.3�� reprenons l’exemple de l’exercice 7.8. Il s’agissait de construire un automate fini non-d�terministe reconnaissant les mots de l’alphabet {a,b} qui terminent par bab. L’automate suivant r�pond � la question.

Essayons maintenant de le d�terminiser en construisant un nouvel �tat � partir de chaque sous ensemble d’�tat possible.

Remarquons que les �tats {1}, {2}, {3}, {0,2}, {0,3}, {1,2}, {2,3}, {0,1,2}, {1,2,3}, {0,2,3} sont inatteignables et peuvent �tre “retir�s” de l’automate.

En pratique, lors de la conversion, on ne cr�e pas imm�diatement tous les �tats de l’automate fini d�terministe. Les �tats “utiles” sont cr�es quand on en a besoin en suivant la m�thode de construction ci-dessous :

• Q_d est initialis� � ∅ et soit E un ensemble d’�tats initialis� � E = {{q₀}}
• Tant que E est non vide,
  • choisir un �l�ment S de E (S est donc un sous ensemble de Q_n),
  • ajouter S � Q_d,
  • pour tout symbole a ∈ Σ,
    • calculer l’�tat S′ = ∪_{q ∈ S} δ_n(q, a)
    • si S′ n’est pas d�j� dans Q_d, l’ajouter � E
    • ajouter un arc sur l’automate entre S et S′ et la valuer par a

7.4.3��Les є transitions

Rappelons qu’є repr�sente le mot vide. Une є transition (not�e є sur l’arc d’un automate) permet de passer d’un �tat � l’autre d’un automate sans lire de symbole. Cette facilit� permet de programmer facilement des automates complexes.

Une table de transition peut �tre associ�e � un automate contenant des є transition. La table est identique � celle utilis�e pour un automate fini non-d�terministe � ceci pr�s qu’on la compl�te d’une colonne associ�e au caract�re vide є.

Exemple�7.4�� Pour illustrer les є transitions, construisons un automate fini non d�terministe qui reconna�t les nombres d�cimaux. Rappelons qu’un nombre d�cimal est un nombre r�el qui est le quotient d’un entier relatif par une puissance de dix. Plus pr�cis�ment, on souhaite pouvoir �crire le nombre d�cimal en commen�ant par un “+” ou un “-’, suivi d’une suite de chiffres, d’une virgule et d’une suite de chiffres. Bien entendu, le “+” ou le “-” sont optionnels, la premi�re cha�ne de chiffres ne peut pas �tre vide et ne commence pas par “0” (sauf si le nombre d�cimal est 0). La seconde cha�ne ne se termine pas par “0”. Si seconde cha�ne est vide, on omet la “,”.

La transition de l’�tat A � l’�tat B est r�gie par є,+,−. Ainsi, on peut passer de A � B soit en lisant +, soit en lisant − soit enfin en ne lisant rien.

La table de transition associ�e � cet automate est alors :

	є	+	−	,	0	1	2	⋯	9
→ A	{B}	{B}	{B}	∅	∅	∅	∅	⋯	∅
B	∅	∅	∅	∅	{F}	{C}	{C}	⋯	{C}
C	∅	∅	∅	{D}	{C}	∅	∅	⋯	∅
D	∅	∅	∅	∅	{D}	{D,E}	{D,E}	⋯	{D,E}
* E	∅	∅	∅	∅	∅	∅	∅	⋯	∅
* F	∅	∅	∅	∅	∅	∅	∅	⋯	∅

L’introduction des є transition ne change pas la nature des langages reconnus par les automates. Comme pour les automates non-d�terministes que l’on peut toujours d�terminiser, il est toujours possible d’�liminer les є transition et d’obtenir un automate fini d�terministe �quivalent. Nous n’aborderons pas ici cette �limination.

7.5��Automates finis et expressions r�guli�res

Les automates finis et les expressions r�guli�res ont la m�me expressivit�. En effet, le th�or�me d’�quivalence des expressions r�guli�res et des automates finis (Kleene) �tablit que Le langage accept� par un automate fini correspond � la valeur d’une expression r�guli�re et r�ciproquement.

7.6��Un peu de Java

Il est ais� de repr�senter les automates finis sous la forme d’un programme java. Notre objectif est de

• mod�liser un automate fini non-d�terministe (sans є transition)
• et d’�crire un programme qui d�termine si une cha�ne de caract�re est reconnue par l’automate.

Sans perte de g�n�ralit�, nous allons supposer que l’alphabet est l’ensemble des caract�res ASCII et que les �tats sont num�rot�s � partir de 0.

7.6.1��Mod�le

Le mod�le de donn�es est alors tr�s simple :

• L’�tat initial de l’automate est indiqu� par un entier q0.
• La table de transition delta est un tableau bidimensionnel de listes d’entiers (la liste d’entier �tant ici le moyen le plus simple de repr�senter un ensemble d’�tats). Ainsi delta[q][c] est la liste des �tats atteignables � partir de q en lisant le caract�re c.
• L’ensemble des �tats finaux est une liste d’entiers.
• Enfin, le mot que l’on cherche � reconna�tre est une cha�ne de caract�res String mot.

Soit donc en Java les deux classes List et Automate.

7.6.2��Algorithme de recherche

Nous aurons besoin de quelques fonctions classiques sur les listes

La fonction accepter(String mot, Automate a) qui permet de v�rifier qu’un mot mot est accept� apr l’automate a appelle la fonction static boolean accepter(String mot, Automate a, int i, int q).

La fonction static�boolean�accepter(String�mot,�int�i,�Automate�a,�int�q) prend, en plus de l’automate et du mot que l’on �tudie, deux autres param�tres :

• La position du caract�re courant i dans le mot.
• L’�tat courant q.

Elle renvoie true si et seulement si le sous-mot de mot dont on a retir� les i premiers caract�res �tait reconnu par un automate semblable � a dont l’�tat initial serait q.

Remarquons que si i est le dernier caract�re du mot (ce qui correspond au test if�(i�==�mot.length())) alors il suffit de tester l’appartenance de q � a.finaux. Si ce n’est pas le cas, on va essayer d’emprunter toutes les transitions possibles. on explore ainsi tous les �tats nv_q.val atteignable � partir de q en lisant c. Une fois dans l’�tat nv_q.val, on appelle r�cursivement accepter.

7.6.3��Mise en œuvre sur un automate

Consid�rons l’automate suivant qui accepte toutes les cha�nes qui se terminent par “01”.

La table associ�e � cet automate est alors :

Pour le construire, il nous suffit de construire la table de transition.

Remarquons que le code ASCII du caract�re ’0’ est obtenu par (int)’0’.