Langage reconnu par un automate

Soyez le premier à donner votre avis sur cette source.

Vue 15 564 fois - Téléchargée 1 402 fois

Description

Un petit programme qui lit un automate dans un fichier, le format est dans la partie
.
Pour lancer le programme, "drag-and'droper" un fichier sur le ".exe" (au passage ".ex"=>".exe").

Une fois l'automate lu, le programme affiche l'automate avec les transitions, et affiche le resultat des tests des exemples.
Les tests consistent à tester (sans blague !) sir un mot appartient au langage de l'automate.

Le gros travail du programme est de calculer le langage reconnu par l'automate. Pour cela il suffit de resoudre un systeme
d'equation mit sous forme matriciel, puis de la resoudre en rendant la matrice triangulaire (ca doit rappeller le pivot de Gauss)

Le programme est fragile au point de vu est erreur d'entree, il ne teste pas si les donnees sont erronees, il suppose qu'elle le sont. De plus il suppose que l'automate est deterministe et émondé !!

Source / Exemple :

<code basic> taille_alphabet=3 a RGB(255,0,0) b RGB(0,255,0) c RGB(0,0,255) nombre_sommets=3 nombre_transitions=3 a:0->1 b:1->1 c:1->2 nombre_exemples=5 abc abbbc abca ac abbbbbbbbbbbbbbbbbbbba ----------------------------------------------------- taille_alphabet=2 a RGB(255,0,0) b RGB(0,0,255) nombre_sommets=2 nombre_transitions=4 a:0->1 a:1->0 b:0->0 b:1->1 nombre_exemples=10 a aa aaa b bb bbb aba bab abababab ababababa ----------------------------------------------------- taille_alphabet=2 a RGB(255,0,0) b RGB(0,0,255) nombre_sommets=4 nombre_transitions=8 a:0->1 a:1->0 a:2->3 a:3->2 b:0->2 b:2->0 b:1->3 b:3->1 nombre_exemples=10 a aa aaa b bb bbb aba bab abababab ababababa ----------------------------------------------------- taille_alphabet=2 a RGB(255,0,0) b RGB(0,0,255) nombre_sommets=4 nombre_transitions=8 a:0->1 a:1->0 a:2->3 a:3->2 b:0->2 b:2->0 b:1->3 b:3->1 nombre_exemples=10 a aa aaa b bb bbb aba bab abababab ababababa ----------------------------------------------------- taille_alphabet=3 a RGB(255,0,0) b RGB(0,255,0) c RGB(0,0,255) nombre_sommets=2 nombre_transitions=5 a:0->0 c:0->0 a:1->1 c:1->1 b:0->1 nombre_exemples=5 abc abbbc abca ac abcca ----------------------------------------------------- taille_alphabet=2 0 RGB(255,128,0) 1 RGB(255,0,255) nombre_sommets=4 nombre_transitions=8 0:0->3 1:0->1 0:3->3 1:3->1 0:1->2 1:1->3 0:2->1 1:2->1 nombre_exemples=5 0101 11 110000 110011 101010 ----------------------------------------------------- taille_alphabet=7 A RGB(255,0,0) B RGB(0,255,0) E RGB(0,0,255) G RGB(255,0,255) J RGB(255,255,0) Y RGB(0,255,255) _ RGB(0,0,0) nombre_sommets=10 nombre_transitions=11 J:0->1 E:1->2 _:2->3 J:2->1 B:3->4 E:4->5 G:5->6 A:6->7 Y:7->8 E:8->9 B:9->4 nombre_exemples=6 JE BEGAYE JE_BEGAYE JEJE_BEGAYE JE_BEGAYE_JE_BEGAYE JEJE_BEGAYEBEGAYEBEGAYE

Conclusion :


Pour information, pour obtenir le systeme d'equations (une par etat de l'automate).
S'il y a une transition de E vers E' par la lettre <a>, alors le langage reconnu par E notée L est L=a.L'
S'il y a deux transition : E->E' avec <a> et E->E'' avec <b> alors L=a.L' + b.L''
On obtient un system d'equation.
Les coefficients de la matrice sont des expressions "formelles". L'operation '.' n'est pas commutative !!!
De plus si l'on a L=a.L+e alors L=(a*).e ou a* represente toutes les puissances iterees de <a>
Ceci est l'equivalent de l'inverse, c'est ce qui permet d'eliminer les elements diagonaux de la matrice.

Bon si vous avez des questions ...

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

yahia256
Messages postés
2
Date d'inscription
jeudi 31 janvier 2013
Statut
Membre
Dernière intervention
31 janvier 2013
-
j'arrive pas a ouvrir ton truc.. comment ça fonctionne ??
nadjet24
Messages postés
31
Date d'inscription
mercredi 12 décembre 2007
Statut
Membre
Dernière intervention
8 mai 2008
-
Bonjour je trouve votre programme interessant.Je souhaite encore avoir une petite d'aide car j'ai un fichier XML je souhaite le convertit en machine à état finis pour l'implementer en suite par les workFlow voilà mon fichier xml en arboressence merci infiniment.


-









-
timeToPerform = Period: 2 days from start of transaction










-
-


-



-
-


-



-
-




-
-




-
-


-

cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
je trouve le programme plutôt impressionnant. hmm, évidemment ça l'aurait été encore plus si tu arrivais à construire la FSM (automate donc) à partir de sa description par expressions régulières (je sais que c'est pas comme ça qu'on dit en français... mais je sais plus comment on le dit en français ^^) ... mais le truc chaud avec les regexp, c'est qu'il est indispensable de simplifier la FSM obtenue, et ça c'est :/.
magic_Nono
Messages postés
1878
Date d'inscription
jeudi 16 octobre 2003
Statut
Membre
Dernière intervention
16 mars 2011
1 -
Vecchio
effectivement, je m'excuse si j'ai été trop incisif.
ce que je me rappelle des cours de TdL, c'est que les automates non terminaux (pouvant partir en boucle) sont dangereux, tout au moins pour la génération de langage,
apres, pour l'exploitation, je ne sais plus, mais il me semble qu'on m'a eu mis en garde pour le même soucis, à l'époque...
Je me souviens avoir alors mis en place un systême de validation d'automate qui était relativement complexe. (de mémoire, c'était fait en prolog) et il me semble également que les traductions de prolog à C/C++ donnent en général un très long code.

sinon, évidemment, oui, on apprécie ses efforts explicatifs.

Cordialement.
vecchio56
Messages postés
6539
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7 -
magic_Nono> Pourquoi les automates comportant des boucles seraient-ils mauvais?

Par ailleurs, je trouve tous les commentaires un peu déplacés. Il y a certes quelques fautes, mais l'auteur fait comme toujours un effort pour expliquer le fonctionnement du programme, ce qui est plutot rare.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.