Théorie des langages : Cours minimisation des automates finis déterministes
Télécharger PDFMinimisation des Automates Finis Déterministes
M. Adil KENZI
Théorie des langages
Introduction
La minimisation d’un automate fini déterministe consiste à trouver un automate déterministe avec un nombre minimal d’états qui reconnaît le même langage.
Pour chaque automate fini déterministe, nous pouvons trouver un automate fini déterministe ayant un minimum d’états.
En réalité, l’automate fini est unique : pour deux automates finis déterministes, nous pouvons trouver une méthode pour renommer leurs états, rendant ainsi les deux automates identiques.
Idée de base
1. Trouver les états équivalents en utilisant un algorithme donné.
2. L’automate minimal regroupe les états équivalents.
Définitions
Deux états p et q d’un automate fini déterministe A sont dits équivalents si pour tout mot w de l’alphabet Σ*, δ(p, w) est un état final si et seulement si δ(q, w) est un état final.
Deux états p et q de A sont dits distingués s’ils ne sont pas équivalents.
Les états p et q sont distingués si :
- w = ε, et si p ∈ F (états finaux) tandis que q ∉ F, alors p et q sont distingués (non équivalents).
- w ≠ ε, et si δ(p, w) = r et δ(q, w) = s, et que r et s sont distingués, alors p et q sont distingués.
Algorithme de minimisation
1. Créer un tableau associé à l’automate à minimiser.
2. Marquer les paires d’états (p, q) pour chaque p ∈ F (états finaux) et q ∉ F.
3. Pour chaque paire non marquée (p, q) et chaque symbole a :
- Calculer r = δ(p, a) et s = δ(q, a).
- Si la paire (r, s) est marquée, alors marquer (p, q) ainsi que toutes les paires dépendantes.
- Si la paire (r, s) n’est pas marquée, ajouter (p, q) à la liste des paires dépendantes de (r, s).
Illustration de l’algorithme de minimisation à travers un exemple
Considérons un automate fini déterministe avec les états a, b, c, d, e, f, g, h et les transitions suivantes :
- δ(a, 0) = a, δ(a, 1) = e
- δ(b, 0) = c, δ(b, 1) = g
- δ(c, 0) = c, δ(c, 1) = c
- δ(d, 0) = b, δ(d, 1) = g
- δ(e, 0) = e, δ(e, 1) = b
- δ(f, 0) = c, δ(f, 1) = g
- δ(g, 0) = g, δ(g, 1) = c
- δ(h, 0) = g, δ(h, 1) = c
Les états finaux sont F = {a, e, g}.
Étapes de l’algorithme
1. Création d’un tableau où toutes les paires d’états sont initialement non marquées.
2. Marquer les paires (p, q) où p ∈ F et q ∉ F.
3. Pour chaque paire non marquée et chaque symbole, vérifier les transitions :
- Comparaison des transitions δ(b, 0) ≅ δ(a, 0) et δ(b, 1) ≅ δ(a, 1).
- Comparaison des transitions δ(d, 0) ≅ δ(a, 0) et δ(d, 1) ≅ δ(a, 1).
- Comparaison des transitions δ(e, 0) ≅ δ(a, 0) et δ(e, 1) ≅ δ(a, 1).
- Comparaison des transitions δ(f, 0) ≅ δ(a, 0) et δ(f, 1) ≅ δ(a, 1).
- Comparaison des transitions δ(g, 0) ≅ δ(a, 0) et δ(g, 1) ≅ δ(a, 1).
- Comparaison des transitions δ(h, 0) ≅ δ(a, 0) et δ(h, 1) ≅ δ(a, 1).
- Comparaison des transitions δ(d, 0) ≅ δ(b, 0) et δ(d, 1) ≅ δ(b, 1).
- Comparaison des transitions δ(e, 0) ≅ δ(b, 0) et δ(e, 1) ≅ δ(b, 1).
- Comparaison des transitions δ(f, 0) ≅ δ(b, 0) et δ(f, 1) ≅ δ(b, 1).
- Comparaison des transitions δ(g, 0) ≅ δ(b, 0) et δ(g, 1) ≅ δ(b, 1).
- Comparaison des transitions δ(h, 0) ≅ δ(b, 0) et δ(h, 1) ≅ δ(b, 1).
Les états équivalents sont regroupés comme suit : {a, e}, {b, h}, {c}, {d, f}, {g}.
Automate minimal
- État initial : a
- Transitions :
- δ(a, 0) = a, δ(a, 1) = b
- δ(b, 0) = c, δ(b, 1) = g
- δ(c, 0) = c, δ(c, 1) = c
- δ(d, 0) = b, δ(d, 1) = g
- δ(g, 0) = g, δ(g, 1) = c
FAQ
Qu’est-ce qu’un automate fini déterministe minimal ?
Un automate fini déterministe minimal est une version simplifiée d’un automate fini déterministe qui reconnaît le même langage avec le nombre minimal d’états possibles.
Pourquoi minimiser un automate fini déterministe ?
La minimisation d’un automate fini déterministe permet de réduire sa complexité, d’améliorer sa lisibilité et de faciliter son implémentation en optimisant le nombre d’états.
Comment identifier les états équivalents dans un automate fini déterministe ?
Les états équivalents sont identifiés en utilisant un algorithme qui compare les transitions des paires d’états pour vérifier si elles mènent à des états finaux identiques ou distingués.