Théorie des langages : Cours automate 7
Télécharger PDFChapitre 7 : Les automates
7.1 Pourquoi étudier les automates
Ce chapitre présente une introduction succincte à la théorie des automates, un concept fondamental en informatique. Les automates, objets mathématiques, permettent de modéliser de nombreux systèmes informatiques. Leur étude, débutée à la fin des années 1950, s’appuie sur des techniques variées comme la topologie, la théorie des graphes, la logique ou encore l’algèbre.
De manière informelle, un automate est un ensemble d’états reliés par des transitions marquées par des symboles. Lorsqu’un mot est fourni en entrée, l’automate lit ses symboles un par un et passe d’un état à un autre selon les transitions. Le mot est alors soit accepté, soit rejeté.
Voici quelques exemples classiques d’utilisation des automates :
- Vérification de circuits électroniques
- Recherche d’occurrences dans un texte (comme les moteurs de recherche)
- Vérification de protocoles de communication
- Compression de données
- Compilation
- Biologie (notamment en génomique)
En dehors de ces applications pratiques, les automates sont aussi utilisés pour modéliser les ordinateurs et analyser leurs capacités : ce qu’ils peuvent décider (décidabilité) et ce qu’ils peuvent faire efficacement (complexité).
7.2 Rappel : alphabets, mots, langages et problèmes
Nous reprenons ici les notations du chapitre précédent.
Un alphabet Σ est un ensemble fini de caractères ou symboles. Un mot est une séquence finie de ces caractères. L’ensemble de tous les mots sur Σ est noté Σ*. Un langage est un sous-ensemble de Σ*, c’est-à-dire un ensemble de mots spécifiques.
Parmi les mots de Σ*, on distingue le mot vide, noté ε, qui est le seul mot de longueur zéro.
7.3 Automates finis déterministes
Un automate fini déterministe est défini par un quintuplé (Q, Σ, δ, q₀, F), où :
- Q est un ensemble fini d’états.
- Σ est un alphabet fini.
- δ est une fonction de transition (δ : Q × Σ → Q).
- q₀ est l’état initial (q₀ ∈ Q).
- F est un ensemble d’états finaux ou acceptants (F ⊆ Q).
7.3.1 Fonctionnement d’un automate fini déterministe
Un automate fini déterministe accepte ou rejette un mot en entrée. Il reconnaît un langage composé de tous les mots qu’il accepte.
Le processus de reconnaissance se déroule comme suit :
- L’automate commence dans l’état initial q₀.
- Il lit les symboles du mot un par un.
- À chaque symbole, il utilise la fonction de transition δ pour passer à l’état suivant, basé sur l’état actuel et le symbole lu.
- Le mot est accepté si et seulement si l’état final, après la lecture du dernier symbole, appartient à F.
Pour définir précisément le langage L(A) reconnu par un automate fini déterministe A = (Q, Σ, δ, q₀, F), on utilise une fonction de transition étendue aux mots, notée δ. Elle est définie récursivement :
- Pour un état q et le mot vide ε, δ(q, ε) = q (l’automate reste dans le même état).
- Pour un mot c = c' a (où c' ∈ Σ* ∪ {ε} et a ∈ Σ), δ(q, c) = δ(δ(q, c'), a).
Le langage accepté est alors : L(A) = {c | δ(q₀, c) ∈ F}.
7.3.2 Représentations compactes des automates
Un automate fini déterministe peut être représenté par une table de transition où :
- Les colonnes correspondent aux symboles de l’alphabet Σ.
- Les lignes correspondent aux états de Q (l’état initial est marqué par une flèche →, et les états finaux par une étoile *).
- L’intersection d’une ligne q et d’une colonne a indique l’état δ(q, a).
Exemple : Considérons la table suivante :
| a | b | |
| → | 1 | 2 |
| 1 | 1 | 2 |
| * | 2 | 2 |
Cet automate est défini par :
- Q = {1, 2}
- Σ = {a, b}
- δ(1, a) = 1, δ(1, b) = 2, δ(2, a) = 1, δ(2, b) = 2
- q₀ = 1
- F = {2}
Il reconnaît les mots sur {a, b} qui se terminent par un b.
Un automate peut aussi être représenté par un graphe de transition où :
- Les sommets correspondent aux états Q.
- Les arcs entre les sommets sont étiquetés par les symboles de Σ.
- L’état initial q₀ est marqué par une flèche entrante.
- Les états finaux F sont entourés d’une double ligne.
Pour simplifier, un arc peut être étiqueté par plusieurs symboles séparés par des virgules.
7.4 Automates finis non-déterministes
Un automate fini non-déterministe est un automate où, dans un état donné, plusieurs transitions peuvent exister pour un même symbole. Son fonctionnement n’est donc pas totalement déterminé.
Un automate fini non-déterministe est défini par un quintuplé (Q, Σ, δ, q₀, F), où :
- Q est un ensemble fini d’états.
- Σ est un alphabet fini.
- δ est une fonction de transition (δ : Q × Σ → P(Q)), où P(Q) est l’ensemble des sous-ensembles de Q.
- q₀ est l’état initial.
- F est un ensemble d’états finaux.
Tout automate fini déterministe est aussi un automate fini non-déterministe. Les tables de transition pour les automates non-déterministes contiennent des sous-ensembles d’états.
7.4.1 Fonctionnement d’un automate fini non-déterministe
Un automate fini non-déterministe accepte ou rejette un mot en entrée, tout comme un automate déterministe. Le langage associé est l’ensemble des mots qu’il reconnaît.
Exemple : Voici un automate qui reconnaît les mots sur l’alphabet {a, b, c} commençant par a et finissant par c.
| a | b | c | |
| → | {q₁} | ∅ | ∅ |
| q₁ | {q₁} | {q₁} | {q₁, q₂} |
| * | q₂ | ∅ | ∅ |
La fonction de transition étendue δ est définie récursivement :
- Pour un état q et le mot vide ε, δ(q, ε) = {q} (l’automate reste dans le même état).
- Pour un mot c = c' a (où c' ∈ Σ* ∪ {ε} et a ∈ Σ), δ(q, c) = ∪ {δ(p, a) | p ∈ δ(q, c')}.
Le langage reconnu est : L(A) = {c | δ(q₀, c) ∩ F ≠ ∅}.
7.4.2 Déterminisation d’un automate fini non-déterministe
Tout langage reconnu par un automate fini non-déterministe peut aussi être reconnu par un automate fini déterministe (théorème de Rabin-Scott). Pour convertir un automate fini non-déterministe Aₙ = (Qₙ, Σ, δₙ, q₀, Fₙ) en un automate fini déterministe Aᵈ = (Qᵈ, Σ, δᵈ, {q₀}, Fᵈ), on procède comme suit :
- L’alphabet Σ reste inchangé.
- L’état initial de Aᵈ est {q₀}.
- Qᵈ est l’ensemble de tous les sous-ensembles de Qₙ.
- Fᵈ est l’ensemble des sous-ensembles de Qₙ contenant au moins un état de Fₙ.
- Pour un sous-ensemble S de Qₙ et un symbole a ∈ Σ, δᵈ(S, a) = ∪ {δₙ(q, a) | q ∈ S}.
En pratique, on ne construit pas tous les états de Qᵈ dès le début. On crée seulement les états "utiles" en suivant une méthode itérative.
7.4.3 Les transitions ε
Une transition ε permet à un automate de passer d’un état à un autre sans lire de symbole. Elle facilite la construction d’automates complexes.
Les tables de transition pour les automates avec transitions ε incluent une colonne supplémentaire pour le symbole vide ε.
Exemple : Un automate fini non-déterministe qui reconnaît les nombres décimaux (avec ou sans signe, une partie entière et une partie décimale).
7.5 Automates finis et expressions régulières
Les automates finis et les expressions régulières ont la même expressivité. Le théorème de Kleene établit que tout langage reconnu par un automate fini peut être décrit par une expression régulière, et réciproquement.
7.6 Un peu de Java
Les automates finis peuvent être implémentés en Java. Voici une approche pour modéliser un automate fini non-déterministe (sans transitions ε) et vérifier si une chaîne est acceptée.
7.6.1 Modèle
On utilise deux classes : Liste pour représenter les états et Automate pour modéliser l’automate.
Liste :
class Liste {
int val;
Liste suivant;
Liste(int v, Liste x) {
val = v;
suivant = x;
}
}
Automate :
class Automate {
int q0;
Liste[][] delta;
Liste finaux;
Automate(int q, Liste f, Liste[][]d) {
q0 = q;
delta = d;
finaux = f;
}
}
7.6.2 Algorithme de recherche
On implémente des fonctions utilitaires pour manipuler les listes, comme longueur, kieme et estDans.
static int longueur(Liste x) {
if (x == null)
return 0;
else
return 1 + longueur(x.suivant);
}
static int kieme(Liste x, int k) {
if (k == 1)
return x.val;
else
return kieme(x.suivant, k - 1);
}
static boolean estDans(Liste x, int v) {
if (x == null)
return false;
else
return x.val == v || estDans(x.suivant, v);
}
La fonction accepter vérifie si un mot est reconnu par l’automate :
static boolean accepter(String mot, Automate a) {
return accepter(mot, a, 0, a.q0);
}
static boolean accepter(String mot, Automate a, int i, int q) {
if (i == mot.length())
return Liste.estDans(a.finaux, q);
else {
boolean resultat = false;
int c = mot.charAt(i);
for (Liste nv_q = a.delta[q][c]; nv_q != null; nv_q = nv_q.suivant)
resultat = resultat || accepter(mot, a, i + 1, nv_q.val);
return resultat;
}
}
7.6.3 Mise en œuvre sur un automate
Exemple : Un automate qui reconnaît les chaînes se terminant par "01". La table de transition est :
| 0 | 1 | |
| → | {0, 1} | {0} |
| 1 | ∅ | {2} |
| * | 2 | ∅ |
public static void main(String[] arg) {
Liste[][] delta = new Liste[3][128];
delta[0][(int)'0'] = new Liste(0, new Liste(1, null));
delta[0][(int)'1'] = new Liste(0, null);
delta[1][(int)'0'] = null;
delta[1][(int)'1'] = new Liste(2, null);
delta[2][(int)'0'] = null;
delta[2][(int)'1'] = null;
Automate a = new Automate(0, new Liste(2, null), delta);
System.out.println("accepter = " + accepter(arg[0], a));
}
FAQ
Qu’est-ce qu’un automate fini déterministe ?
Un automate fini déterministe est un modèle mathématique où, pour chaque état et chaque symbole, il existe une seule transition possible. Il est défini par un ensemble d’états, un alphabet, une fonction de transition unique, un état initial et des états finaux.