Automates non déterministes et déterminisation
L'automate non déterministe : plusieurs transitions possibles, ε-transitions et ε-fermeture, acceptation par chemin, ensemble d'états actifs et construction des sous-ensembles qui le rend déterministe.
- 24 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Automate non déterministe : de quoi s'agit-il ?
Voir la réponse
Automate où un état peut avoir zéro, une ou plusieurs transitions pour une même lettre, et plusieurs états initiaux.
Il n'a pas plus de puissance qu'un déterministe : les deux reconnaissent exactement les langages réguliers. Il est souvent bien plus petit à écrire.
Quand un automate non déterministe accepte-t-il un mot ?
- S'il existe au moins un chemin étiqueté par le mot qui mène à un état acceptant
- Si tous les chemins étiquetés par le mot mènent à un état acceptant
- Si un état acceptant est visité à un moment de la lecture
- Si le premier chemin essayé mène à un état acceptant
Voir la réponse
S'il existe au moins un chemin étiqueté par le mot qui mène à un état acceptant
« Il existe » et non « pour tous ». Passer par un état acceptant en cours de lecture ne suffit pas, il faut y finir. Et il n'y a pas d'ordre d'essai : tous les chemins comptent.
Dans la construction des sous-ensembles, l'état initial est l'ensemble des états …, et un ensemble est acceptant s'il contient au moins un état ….
Voir la réponse
Dans la construction des sous-ensembles, l'état initial est l'ensemble des états initiaux, et un ensemble est acceptant s'il contient au moins un état acceptant.
Un ensemble d'états actifs représente tous les chemins possibles à la fois : il suffit qu'un seul soit acceptant pour que le mot soit accepté.
ε-transition : de quoi s'agit-il ?
Voir la réponse
Transition étiquetée ε, qu'on peut emprunter sans lire aucune lettre.
Elle est pratique pour assembler des automates (union, étoile) comme dans la construction de Thompson, mais s'élimine toujours sans changer le langage.