Bonjour,
Dans notre leçon précédente, nous avons développé la méthodologie pour construire un automate fini déterministe (AFD) à partir d'une description de langage. Nous avons insisté sur le fait que la rigueur d'un AFD provient de sa nature déterministe : pour chaque état et chaque symbole, une et une seule transition est possible.
Aujourd'hui, nous allons assouplir ces contraintes en introduisant le concept de non-déterminisme. L'objectif est de définir formellement ce qu'est un automate fini non-déterministe (AFN) et de comprendre précisément en quoi il diffère d'un AFD. Cette notion, loin d'être un simple artifice théorique, est un outil puissant qui simplifie considérablement la conception d'automates pour de nombreux langages.
1. L'Intuition du Non-Déterminisme : Le Pouvoir du "Choix"
Pourquoi introduire le non-déterminisme ? Car il nous permet de concevoir un automate en adoptant une perspective différente : au lieu de devoir gérer tous les cas à chaque étape, l'automate peut "deviner" ou "choisir" le bon chemin.
Imaginez que vous deviez construire un automate qui reconnaît les mots sur {a, b} se terminant par abb.
Avec un AFD, vous devriez gérer méticuleusement chaque possibilité : "ai-je vu un a ?", "ai-je vu ab ?", "ai-je vu aba et dois donc tout recommencer ?".
Avec un AFN, l'idée est plus simple :
- On reste dans un état initial tant qu'on ne "décide" pas que la fin
abbcommence. - À un moment donné, sur un
a, l'automate "choisit" de passer à un état suivant, espérant que la suite serabb. - Si la suite est bien
bb, le mot est accepté.
C'est comme si l'automate explorait plusieurs chemins de calcul en parallèle et acceptait le mot si au moins un de ces chemins mène à un état final.
L'automate ci-dessous illustre parfaitement cette idée pour le langage des mots se terminant par abb sur l'alphabet {a, b}.
Ce "choix" est la marque du non-déterminisme. La vidéo suivante identifie les deux sources formelles de ce non-déterminisme.
#18 Théorie des Langages et Compilation- Automates à États Finis- Partie 1
Cette vidéo de Bouchra Bouihi, issue d'un cours sur la Théorie des Langages, va nous permettre d'identifier précisément ce qui rend un automate non-déterministe. Portez attention aux deux conditions mentionnées.
Regardez la section de 23:14 à 25:37. L'intervenante y définit un automate fini non-déterministe (AFN) en listant deux conditions suffisantes : la présence de plusieurs états initiaux, ou l'existence de plusieurs transitions possibles pour un même symbole depuis un même état.
Pour résumer, un automate est non-déterministe si au moins l'une de ces conditions est vraie :
- Il a plusieurs états initiaux.
- Depuis un état donné, il existe plusieurs transitions sortantes étiquetées par le même symbole.
Une troisième source de non-déterminisme, mentionnée dans la vidéo à 26:51, est la possibilité de transitions spontanées (ou -transitions), qui permettent de changer d'état sans consommer de symbole en entrée. Nous y reviendrons.
L'image suivante met en évidence ces différences de manière saisissante.
2. La Définition Formelle de l'AFN
Maintenant que l'intuition est posée, il nous faut la rigueur mathématique exigée au concours. Comme pour l'AFD, un AFN est un quintuplet, mais avec une différence fondamentale dans la fonction de transition.
Le document ci-dessous formalise cela de manière très claire.
[PDF] 3. Non déterminisme - Arnaud Casteigts
Ces notes de cours d'Arnaud Casteigts (Université de Bordeaux) présentent la définition formelle de l'AFN. L'objectif est de comprendre comment la fonction de transition est modifiée pour capturer le non-déterminisme.
Lisez la section 3.1.1 'Définition formelle'. Notez la définition du 5-tuple (Q, Σ, δ, q0, F) et concentrez-vous sur la signature de la fonction de transition δ.
Comme vous l'avez lu, la définition est :
Un AFN est un 5-tuple où :
- est un ensemble fini d'états.
- est un alphabet.
- est la fonction de transition.
- est l'état initial.
- est l'ensemble des états finaux.
La différence cruciale est la fonction de transition . Au lieu de retourner un seul état (un élément de ), elle retourne un ensemble d'états (un élément de , l'ensemble des parties de ). Cet ensemble peut être vide, un singleton, ou contenir plusieurs états.
Mais pourquoi précisément ? La vidéo suivante offre une justification combinatoire lumineuse.
Formal Definition of Non-Deterministic Finite Automata (NFA)
Cette vidéo de Neso Academy, bien qu'en anglais, explique de manière remarquable pourquoi le codomaine de la fonction de transition d'un AFN est l'ensemble des parties de Q. La démonstration est visuelle et mathématique, et constitue un excellent exercice de compréhension profonde.
Regardez la section de 03:43 à 09:57. L'objectif est de suivre le raisonnement qui part des possibilités de transitions (aller vers l'état A, B, A et B, ou nulle part) pour arriver à la conclusion que pour |Q| états, il y a 2^|Q| destinations possibles, ce qui correspond exactement à la taille de l'ensemble des parties P(Q).
3. Synthèse et Contraste Formel avec l'AFD
Nous sommes maintenant armés pour établir une distinction formelle et rigoureuse entre AFD et AFN, en nous appuyant sur une source de référence.
[PDF] Notes de révision : Automates et langages
Les notes de révision pour l'Agrégation de l'ENS Paris-Saclay fournissent des définitions d'une grande précision. Nous allons les utiliser pour contraster les deux types d'automates.
Lisez d'abord la Définition 1.2 (Automate fini), qui présente le cas général, implicitement non-déterministe. Ensuite, lisez la Définition 1.12 (Automate déterministe). Repérez les deux contraintes qui spécialisent le cas général en un automate déterministe.
En analysant ces définitions, nous pouvons dresser un tableau comparatif précis :
| Caractéristique | Automate Fini Déterministe (AFD) | Automate Fini Non-déterministe (AFN) |
|---|---|---|
| États initiaux | Un unique état initial, . | Un ensemble d'états initiaux (souvent un seul par convention). |
| Fonction de transition | ||
| Nature des transitions | Pour tout état et symbole , il y a exactement une destination . | Pour tout état et symbole , est un ensemble de destinations (peut être vide). |
| Transitions spontanées () | Non autorisées. | Autorisées. |
| Exécution | Un seul chemin de calcul pour chaque mot. | Plusieurs chemins de calcul possibles. |
| Acceptation d'un mot | Le chemin unique de calcul pour se termine dans un état final. | Au moins un des chemins de calcul pour se termine dans un état final. |
Il est fondamental de comprendre qu'un AFD est un cas particulier d'AFN. C'est un AFN où l'ensemble des états initiaux est un singleton, où il n'y a pas de -transitions, et où l'image de la fonction de transition est toujours un singleton.
Conclusion
Cette leçon nous a permis de franchir une étape conceptuelle importante en introduisant le non-déterminisme.
Points clés à retenir :
- L'AFN généralise l'AFD en autorisant des "choix" : plusieurs transitions pour un même symbole, ou aucune.
- La différence formelle réside dans la fonction de transition , qui retourne un ensemble d'états () au lieu d'un seul état.
- Les AFN peuvent avoir des -transitions, permettant des changements d'état sans consommer d'entrée.
- Un mot est accepté par un AFN si au moins une de ses exécutions possibles aboutit à un état final.
- Le non-déterminisme est avant tout un outil de simplification de la conception : il est souvent plus naturel de concevoir un AFN qu'un AFD pour un langage donné.
Cette dernière affirmation soulève une question essentielle : si les AFN sont plus flexibles, sont-ils également plus "puissants" ? Peuvent-ils reconnaître des langages que les AFD ne peuvent pas reconnaître ? La réponse, peut-être surprenante, est non. Dans notre prochaine leçon, nous le démontrerons en étudiant la construction des sous-ensembles, un algorithme qui permet de transformer n'importe quel AFN en un AFD équivalent.