Automates Java Fermé

Question

Bonjour, 
J'ai un petit problème avec la déterminisation d'un automate non déterministe, enfaite je voudrais faire un code en java qui reçoit un automate non déterministe, et qui l'a déterminise, j'ai cherché un peux sur le net pour mieux comprendre la déterminisation , mais je trouve que des explications avec des formules mathématique..du coup je comprends pas trop le principe
si quelqu'un peut  m'expliquer l'algorithme de cette déterminisation svp
Merciiiiiiiiiiiiiiiiiiiii

silentData · Answer

Vu se que tu cherches, je m'orienterais vers le site developpez.com pour ta question... Les membres pourront certainement plus t'aider qu'ici, parce que ta question est assez spécifique...

Pour ma part on voit les automates déterministes au prochain semestre, je peux pas encore t'aider, désolé...

Pedro · Answer

Bonjour,  

Si je me souviens bien pour déterminiser un AFN on peut faire un tableau avec autant de colonnes que de lettre dans l'alphabet   

Ensuite sur la première ligne tu regroupes tous tes états de départ (et leur transitions spontanées) et tu mets dans la colonne correspondant à chaque lettre les états que tu peux atteindre  

Par exemple si tes états de départ sont 1 et 4 ta première ligne sera  

{1,4}  tous les états accessibles depuis 1 et 4 pour chaque lettre de l'alphabet...  

Cette ligne fera apparaitre plusieurs nouvelles classes d'états. Par exemple depuis {1,4} avec le mot A tu arrives en {2,5} et avec le mot B tu arrives en {3}  

Ta seconde ligne sera {2,5}...  
Ta troisième 3...  

En fait tu traites les classes dans leur ordre d'apparition jusqu'à ce qu'il n'y en ait plus à traiter. (n'oublie pas les transitions spontanées pour chaque traitement)  

Tu obtiens ainsi ta table pour ton AFD (chaque classe est un état de ton AFD) 

NB l'état vide (s'il y en a un) sera un piège refusant et tes états acceptants sont tes classes qui contiennent au moins un état acceptant.
Ton état de départ est bien sûr la classe qui regroupe les états de départ de ton AFN.  

Ensuite il faudrait le rendre minimale , mais je te laisse déjà faire ça dans un premier temps. 

J'ai fait ça de mémoire, j'espère qu'il n'y a pas de trous ou d'erreur...  

Ensuite, à toi de choisir pour l'implémentation en java

Automates Java

2 réponses

Discussions similaires