Il s’agit dans cet exercice de réaliser une application
qui a pour rôle de simuler le mécanisme des automates finis non-déterministes
et la reconnaissance des expressions régulières.
En effet, l’application doit:
- lire et accepter une
expression régulière
- générer un automate fini
déterministe reconnaissant cette expression
Structure et stockage dans la mémoire :
Avant
de procéder à la structuration il faut pouvoir préciser le nombre d’états
associés à chaque caractère de l’expression régulière.
Ainsi :
·
a={a-z,A-Z} ;
·
0={0-9} ;
·
*,|,+.
Correspondent à l’ajout de deux états.
·
.,(,).
Ne correspondent à aucun nouvel état.
Ainsi si on prend l’exemple de l’expression régulière
suivante :
·
a|(a.0)
On peut déduire
dès le début le nombre d’états correspondants. Ici, nous avons : 8 états.
Suivant
le même exemple on trouve l’AFN qui suit :
Afin
de structurer l’ensemble des états et des transitions dans la mémoire, on a vu
utile l’utilisation d’une liste chaînée, capable de contenir et de refléter
l’ensemble des états et des transitions au sein d’un automate.
Pour
ce faire on doit allouer un espace dans la mémoire dynamique, accessible via
des pointeurs (Etat t=*e) créés dans la
mémoire statique.
Ainsi, une structure va créer les
dits tableaux :
Structure Etat
debut
T[4] :entier ;
Fin;
Alors
T[1],T[2],T[3],T[4]
correspondent successivement aux adresses
des états correspondants à a,0,ε1,ε2.
On utilise deux ε ; car on
risque d’avoir deux transitions ε.
Cette
structuration, arborescente donne la certitude de bien respecter le
passage correcte à l’issu de chaque transition. Ainsi, une structuration pareille permettra
de réaliser l’application demandée dans cet exercice .