Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Université Mentouri Ȃ Constantine Ȃ Faculté des sciences de lǯingénieur Départe

Université Mentouri Ȃ Constantine Ȃ Faculté des sciences de lǯingénieur Département de lǯinformatique AUTOMATES À ETATS FINIS SOUS --------------LǯOUTIL ATOM3 ------------ NFAǥ..DFAǥ..NFA Æ DFA Réalisé par : BOULESNANE ABDENNOUR EMAIL :noroo.software@gmail.com noro-1989@hotmail.fr 2012- 2012-2013 Page 2 INTRODUCTION : AToM 3 est un outil visuel pour la Modélisation Multi-Paradigme qui possède : Une couche de Méta-modélisation pour la modélisation graphique d'un formalisme (les entités du formalisme, leurs attributs, leurs relations, leurs cardinalités, leurs contraintes, leurs apparences graphiques (syntaxe concrète)). Aussi un système de réécriture de graphes pour les manipulations de modèles par application itérative des règles d¶une Grammaire de Graphes LA Grammaire de graphes dans AToM3 se compose d'une action initiale, d'un ensemble des règles et d'une action finale : -L'action initiale (finale) spécifie les actions à exécuter avant (après) l'application des règles -Les règles sont classées selon des priorités pour diriger le choix de la règle à appliquer. On va voir un exemple sur l¶utilisation de l¶outil Atom3 pour développer un Automate à état finis NFA (Non Déterministe) ou bien DFA (Déterministe) et aussi une transformation d¶un NFA vers DFA. Page 3 1. Le Méta-modèle d¶Automate à état finis : Un méta-modèle est un modèle qui définit précisément les concepts manipulés dans les modèles ainsi que les relations entre ces concepts. Mais aussi il faut assurer que l¶Automate ne continent pas plus d¶un état initial, pour cela on va utiliser cette contrainte : (allez à EDIT--->CONSTRAINTS--->NEW) Aussi l¶Automate il doit contient au moins un état final avec cette contrainte : Page 4 Pour un Automate à état finis déterministe (DFA) il suffit d¶ajouter une contrainte dans la classe « dfastat » : Exemple d¶automate à état finis (NFA) : Exemple d¶automate à état finis (DFA) : En plus pour créer les apparences graphiques des états Initiaux et finaux, on va utiliser les contraintes suivantes : ETAT INITIAL : ETAT FINAL : (gf9 : POLYNINE) (gf4 : OVAL) Page 5 2. La Transformation d¶un NFD vers DFA : À partir d¶un automate à état finis Non déterministe on va avoir un automate à état finis déterministe grâce à un ensemble des règles : 1. Élimine les états inaccessibles. 2. joint les états équivalents. 3. Élimine le non-déterminisme entre deux états différents. 4. Élimine le non-déterminisme dans le même état. 1ére Règle (Élimine les états inaccessibles) : LHS RHS 2 éme Règle (joint les états équivalents) : LHS RHS Condition : node1.in_connection= {} et node1.isInitial=0 Action:/ Condition : node7.condition == node6.condition et node4.condition == node5.condition Action:/ Page 6 3 éme Règle (Élimine le non-déterminisme entre deux états différents) : LHS RHS Initialiser : atom3i : est une instance de la classe ATOM3. On va utiliser atom3i pour pouvoir utiliser les fonctions de la classe ATOM3. Condition : node4.condition == node5.condition Action: pour i in { node2.out_connection et node3.out_connection } Newtrans= Connect (node7, i.out_connection) Newtrans.condition= i.condition Pour j in {node2.in_connection et node3.in_connection} Newtrans =Connect (node7, j.in_connection) Newtrans.condition= j.condition Page 7 Connecter le nouvel état avec les sortis d¶état 2 et état 3 : Connecter le nouvel état avec les entrés d¶état 2 et état 3 : Dans les deux cas on a connecté les états graphiquement grâce à la fonction µshowconnection¶ et au niveau des Objets grâce à µappend¶. 4 éme Règle (Élimine le non-déterminisme dans le même état) : LHS RHS Condition : node3.condition == node4.condition Action:/ Page 8 EXEMPLE : R3---->R1---->R1---->R3---->R1---->R1 Conclusion : à chaque fois il faut trouver les bonnes règles pour aboutir aux meilleurs résultats. uploads/Finance/ automates-a-etats-finis-sous-l-x27-outil-atom3.pdf