e-AFI vers AFD
Nous voulons maintenant montrer que le langage reconnu par un automate avec transitions vides peut également l’être par un automate non-déterministe sans transitions vides (déterminisation e-AFI vers AFD). Cette opération va nécessiter l’addition de nouvelles transitions dans l’automate.
Tout langage reconnu par un AFN avec ε–transitions peut être reconnu par un AFN (sans ε–transitions) ayant le même nombre d’états.
Construction de l’AFN équivalent à un automate avec ε–transitions, en prolongeant δ en δ1 (la fermeture transitive est tous les états qui peuvent être atteint par un état par une transition donnée).
Première étape : Ajout de ε–transitions par fermeture transitive.
Pour tous les états q accessibles à partir de p par ε-transition (en plusieurs étapes), on rajoute une ε–transition directe de p à q. On prolonge ainsi la fonction δ : δ1(p, ε) = tous les états accessibles à partir de p par ε–transition.
Deuxième étape : Ajout de transitions supplémentaires et d’états initiaux supplémentaires, puis suppression des ε-transitions.
Les états initiaux sont tous les états accessibles à partir des états initiaux par ε–transition.
Pour toute transition de p à q par une lettre, on rajoute des transitions de p à r avec la même lettre pour toutes les ε–transitions de q à r : δ1(p, a) = δ(p, a) ∪ ( ∪q∈δ(p, a) δ1(q, ε)).
On supprime toutes les ε–transitions
Exemple
Le principe de l’algorithme consiste à remplacer chaque chemin de longueur 1 commençant par une epsilon-transition par une nouvelle transition qui décrit ce chemin.
Il y a deux chemin de longueur 1 qui commencent par la transition sur epsilon :
- (1, ε, 3)(3, b, 3)
- (1, ε, 3)(3, c, 4)
On ajoute à l’automate deux nouvelles transitions qui résument ces deux chemins :
- (1, b, 3)
- (1, c, 4)
Et on supprime la transition (1, ε, 3).
L’algorithme est un peu plus complexe dans les cas où plusieurs epsilon-transitions se suivent et si elles vont dans un état final, mais le principe général présenté ici reste valable (il suffit d’appliquer la première étape).
L’utilisation des epsilon-transitions permet parfois de décrire plus lisiblement un langage. Elle permet aussi de simplifier la description de certaines opérations (par exemple l’union ou la concaténation -> voir automate de Thompson).
L’existence d’epsilon-transitions rend l’automate non-déterministe puisqu’on a toujours la possibilité d’emprunter une telle transition même quand il existe une transition ordinaire que l’on pourrait emprunter.
Autre exemple
Prenons l’automate suivant :
Pour cela, il faut d’abord calculer, pour chaque état, les ε-successeurs de chaque état p, c’est-à-dire l’ensemble des états q tels qu’il existe un chemin formé uniquement de ε-transitions partant de p arrivant en q.
On calcule les ε-successeurs de chaque état : Succε(p) = {q, r}, Succε(q) = {r}, Succε(r) = ∅.
On obtient l’NFA suivant :
Vous pouvez alors le déterminiser avec la méthode NFA vers DFA, ou alors le déterminiser directement sous sa forme avec espilon transition comme l’exemple suivant.
Reprenons l’automate et transformons-le en un DFA :
La première étape consiste à calculer les epsilon-fermeture pour chaque état de cet automate :
| Delta(Q) | a | b | Fermeture -> Q’ |
| p | p | – | {p,q,r} |
| q | – | q | {q,r} |
| r | r | – | {r} |
Pour chaque état de la fermeture, on calcule ses transitions dans l’alphabet sans epsilon :
| Delta(Q’) | a | b |
| {p,q,r} | {p,r} | {q} |
| {q,r} | {r} | {q} |
| {r} | {r} | – |
Pour chaque état obtenu par les transitions, on calcule la fermeture :
| Delta(Q’) | a | b |
| {p,q,r} | {p,r} -> {p,q,r} | {q} -> {q,r} |
| {q,r} | {r} -> {r} | {q} -> {q,r} |
| {r} | {r} -> {r} | – |
Notons {p,q,r} = P ; {q,r} = Q et{r} = R. Nous obtenons l’automate suivant :
