Théorie des langages : Cours automates finis non déterministes
Télécharger PDFAutomates Finis Non Déterministes
M. Adil KENZI
Théorie des langages
Introduction
Il est difficile de définir des automates finis déterministes reconnaissant des langages donnés, mais les automates non-déterministes simplifient cette tâche.
Pour certains langages, on peut trouver un automate non-déterministe qui les reconnaît et qui est plus petit que tout automate déterministe qui les reconnaît.
Définition des Automates Finis Non Déterministes (NFA)
Un automate fini non déterministe (NFA) est défini comme suit :
NFA : Nondeterministic Finite Automata
Un automate non-déterministe A = <Q, Σ, δ, q₀, F> possède une fonction de transition étendue δ : Q × Σ → P(Q), où P(Q) est l'ensemble des parties de Q.
Plus concrètement, plusieurs arcs reconnaissant le même caractère peuvent « sortir » du même état.
Acceptation d'un mot par un NFA
Un mot est accepté s’il est possible, en partant de l’état initial, d’atteindre un état final en lisant le mot. Même s’il existe d’autres chemins menant à des états non finaux, le mot reste accepté.
C’est la même notion d’acceptation que pour les automates finis déterministes, sauf qu’un automate non déterministe peut offrir plusieurs chemins pour le même mot en raison de son ambiguïté.
Formalisation de l'acceptation
Soit M un automate fini non déterministe M = <Q, Σ, δ, q₀, F>, et soit w = x₁x₂...xₙ un mot où xᵢ ∈ Σ et u ∈ Σ*.
M accepte (ou reconnaît) le mot w si δ(q₀, w) ∩ F ≠ ∅.
Autrement dit, si en appliquant la fonction de transition à partir de l’état initial q₀ avec le mot w, on obtient au moins un état final.
Dans le cas contraire, on dit que l’automate refuse ou rejette la séquence.
Langage reconnu par un NFA
On note par L(M) l’ensemble des mots acceptés par M.
L(M) = { w ∈ Σ* | δ(q₀, w) ∩ F ≠ ∅ }.
On dit que L(M) est le langage reconnu (ou accepté) par M.
Exemple d'acceptation par un NFA
Considérons un automate non déterministe M décrit par le diagramme de transitions suivant :
États : s₀, s₁, s₂, s₃, s₄, s₅, s₆
Transitions :
s₀ → s₁ (a), s₀ → s₂ (a)
s₁ → s₃ (b), s₂ → s₅ (b)
s₃ → s₄ (b), s₅ → s₄ (b)
s₄ → s₅ (b), s₅ → s₆ (a)
s₆ → s₆ (a)
Acceptation du mot "abbbaa"
Voici une suite de transitions menant à l’acceptation du mot "abbbaa" :
s₀ → (a) → {s₁, s₂}
s₁ → (b) → {s₃}, s₂ → (b) → {s₅} → {s₃, s₅}
s₃ → (b) → {s₄}, s₅ → (b) → {s₄, s₅} → {s₄, s₅}
s₄ → (b) → {s₅}, s₅ → (b) → {s₅} → {s₅}
s₅ → (a) → {s₆} → {s₆}
s₆ → (a) → {s₂, s₆}
Le mot est accepté car il existe une suite de transitions menant de l’état initial s₀ à l’état final s₆. Par exemple : s₀ → a → s₂ → b → s₅ → b → s₅ → b → s₅ → a → s₆ → a → s₆.
Même si l’automate peut atteindre l’état non final s₂ en suivant un autre chemin, la séquence est acceptée.
Rejet du mot "abbbb"
Pour le mot "abbbb", aucune suite de transitions ne permet d’atteindre un état final à partir de s₀, donc ce mot est rejeté.
Exercice : Vérification de mots
Soit un automate M’ décrit par le diagramme de transitions suivant :
États : A, B, C, D, E, F, G, H, I
Transitions :
A → B (1), A → C (1)
B → D (0), C → D (0)
D → E (0), D → B (1)
E → F (1), E → G (1)
F → H (0), G → H (0)
H → H (0)
États finaux : F, H
Vérification des mots
1) Mot "10000" :
Transition : A → B (1) → {B, C}
B → D (0) → {B, D, E}
D → E (0) → {A, E, G, H}
E → F (1) → {F, H}
F → H (0) → {H}
Le mot "10000" est reconnu car il atteint l’état final H.
2) Mot "10011" :
Transition : A → B (1) → {B, C}
B → D (0) → {B, D, E}
D → E (0) → {A, E, G, H}
E → F (1) → {B, C, G, I}
F → H (0) → {F, G, H}
Le mot "10011" est reconnu car il atteint les états finaux F et H.
3) Mot "1101" :
Transition : A → B (1) → {B, C}
B → C (1) → {F}
F → (0) → {}
Le mot "1101" n’est pas reconnu car il n’atteint aucun état final.
Théorème
Pour tout automate fini non déterministe, il existe un automate fini déterministe qui reconnaît exactement le même langage.
Exemple de transformation d'un NFA en un DFA
Considérons un automate fini non déterministe AN = <QN, Σ, δN, qN₀, FN> où QN = {1, 2, 3}, Σ = {a, b}, et FN = {3}.
La construction de l’automate fini déterministe AD = <QD, Σ, δD, qD₀, FD> se fait comme suit :
QD = P(QN) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.
L’alphabet Σ ne change pas.
La fonction de transition δD est définie par :
δD(∅, a) = ∅, δD(∅, b) = ∅
δD({1}, a) = ∅, δD({1}, b) = {2, 3}
δD({2}, a) = ∅, δD({2}, b) = ∅
δD({3}, a) = {1, 2}, δD({3}, b) = ∅
δD({1,2}, a) = ∅, δD({1,2}, b) = {2, 3}
δD({1,3}, a) = {1, 2}, δD({1,3}, b) = {2, 3}
δD({2,3}, a) = {1, 2}, δD({2,3}, b) = ∅
δD({1,2,3}, a) = {1, 2}, δD({1,2,3}, b) = {2, 3}
qD₀ = {qN₀} = {1}
FD = {q ∈ QD | q ∩ FN ≠ ∅} = {{3}, {1,3}, {2,3}, {1,2,3}}
Simplification de l’automate déterministe
En supprimant les états non accessibles depuis l’état initial, on obtient un automate déterministe simplifié qui reconnaît le langage {b(ab)n | n ∈ ℕ}.
Transformation d’un NFA en un DFA
Soit AN = <QN, Σ, δN, qN₀, FN> un automate fini non déterministe, il existe un automate déterministe AD = <QD, Σ, δD, qD₀, FD> tel que L(AN) = L(AD).
QD est un sous-ensemble de P(QN), où tous les éléments de P(QN) sont accessibles depuis l’état initial qD₀.
La fonction de transition δD est définie par : δD(qD ∈ QD, a ∈ Σ) = ∪{δN(qN, a) | qN ∈ qD}.
qD₀ = {qN₀}
FD = {q ∈ QD | q ∩ FN ≠ ∅}.
Remarques
Les langages reconnus par les automates finis non déterministes sont identiques à ceux reconnus par les automates finis déterministes.
Cependant, le nombre d’états dans un DFA peut augmenter exponentiellement par rapport au nombre d’états du NFA correspondant.
Un programme simulant un NFA peut soit explorer les chemins possibles un à un en utilisant des retours en arrière, soit construire le DFA équivalent, ce qui peut nécessiter beaucoup d’espace.
Exercice : Construction d'un DFA
Construire un automate fini déterministe qui accepte les mêmes séquences que l’automate fini non déterministe suivant, où l’alphabet est {a, b} :
États : 1, 2, 3, 4
Transitions :
1 → 2 (a), 1 → 3 (a)
2 → 4 (b), 3 → 4 (b)
4 → 2 (a), 4 → 3 (a)
États finaux : 2, 3
FAQ
Quelle est la différence principale entre un NFA et un DFA ?
Un NFA peut avoir plusieurs transitions pour un même symbole et un même état, alors qu’un DFA a exactement une transition pour chaque symbole et chaque état.
Pourquoi un NFA est-il parfois plus petit qu’un DFA pour le même langage ?
Un NFA peut utiliser des transitions multiples et des états non finaux pour simplifier la reconnaissance de certains langages, ce qui réduit le nombre d’états nécessaires.
Comment vérifier si un mot est accepté par un NFA ?
Il faut explorer toutes les transitions possibles à partir de l’état initial et vérifier si au moins un chemin mène à un état final après avoir lu le mot.