Automates Java
javast
Messages postés
75
Date d'inscription
Statut
Membre
Dernière intervention
-
javast Messages postés 75 Date d'inscription Statut Membre Dernière intervention -
javast Messages postés 75 Date d'inscription Statut Membre Dernière intervention -
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
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
A voir également:
- Automates Java
- Waptrick java football - Télécharger - Jeux vidéo
- Jeux java itel - Télécharger - Jeux vidéo
- Eclipse java - Télécharger - Langages
- Java apk - Télécharger - Langages
- Waptrick java voiture - Télécharger - Jeux vidéo
2 réponses
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é...
Pour ma part on voit les automates déterministes au prochain semestre, je peux pas encore t'aider, désolé...
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
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
merci une autre fois