Langage reconnu par un automate

Soyez le premier à donner votre avis sur cette source.

Vue 15 484 fois - Téléchargée 1 395 fois

Télécharger le projet
Commenter

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 ...
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Commenter la réponse de SpEeDy_Fire
S'inscrire maintenant

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.

Du même auteur (cs_JCDjcd)