Un exemple FSM pas à pas

FSM permet de manipuler des automates finis. L'utilisateur peut décrire un automate avec un fichier texte simple. Prenons l'exemple suivant:

Le format FSM textuel est le suivant: chaque transition est décrite sur une ligne avec l'état de départ, l'état d'arrivée, le symbole étiquetant la transition. Le fait qu'un état est un état final est traduit par une ligne ne comportant que le numéro de cet état. Le premier état mentionné sur la première ligne du fichier est l'état initial.

Pour l'exemple choisi, le fichier texte est le suivant:

0 0 1 
0 1 1
0 2 2
1 0 2
1 2 2
2 2 2
2 0 1
2

Supposons que notre fichier texte s'appelle exemple-1.txt. Il faut d'abord compiler ce fichier, ce qui produit un fichier binaire au format interne FSM, que nous allons appeler exemple-1.fsm. La compilation s'écrit:

fsmcompile exemple-1.txt > exemple-1.fsm

On peut obtenir un dessin représentant l'automate avec la commande suivante (à condition d'avoir installé la librairie graphviz qui fournit la commande dot):

fsmdraw exemple-1.fsm | dot -Tgif > exemple-1.gif

Pour visualiser l'image au format GIF exemple-1.gif, vous pouvez utiliser un navigateur ou la commande display.

On peut utiliser des opérations telles que la déterminisation ou la minimisation.

Essayons de réaliser une minimisation:

> fsmminimize exemple-1.fsm
fsmminimize: FSM must be a deterministic acceptor -- FSMMinimize.

On ne peut minimiser qu'un automate déterministe. Prenons les choses dans le bon ordre:

fsmdeterminize exemple-1.fsm > exemple-1-det.fsm
fsmminimize exemple-1-det.fsm > exemple-1-det-min.fsm

On peut obtenir de l'information sur les automates avec la commande fsminfo.

> fsminfo -n exemple-1.fsm
class                           basic
transducer                      n
# of states                     3
# of arcs                       7
initial state                   0
# of final states               1
# of eps                        0
# of accessible states          3
# of coaccessible states        3
# of connected states           3
# strongly conn components      1
> fsminfo -n exemple-1-det.fsm
class                           basic
transducer                      n
# of states                     4
# of arcs                       8
initial state                   0
# of final states               2
# of eps                        0
# of accessible states          4
# of coaccessible states        4
# of connected states           4
# strongly conn components      1
> fsminfo -n exemple-1-det-min.fsm
class                           basic
transducer                      n
# of states                     2
# of arcs                       4
initial state                   0
# of final states               1
# of eps                        0
# of accessible states          2
# of coaccessible states        2
# of connected states           2
# strongly conn components      1

On peut également produire des fichiers images comme on l'a fait pour le premier automate:

fsmdraw exemple-1-det.fsm | dot -Tgif > exemple-1-det.gif
fsmdraw exemple-1-det-min.fsm | dot -Tgif > exemple-1-det-min.gif

Ce qui nous donne les images suivantes:

Il est également possible de partir de la forme compilée de l'automate pour obtenir le fichier au format texte correspondant:

> fsmprint exemple-1-det-min.fsm
0       0       1
0       1       2
1       0       1
1       1       2
1

Jusqu'ici, on a vu un exemple avec les arcs étiquetés par des entiers. Il est possible d'avoir des étiquettes textuelle en utilisant un fichier annexe établissant une correspondance entre les étiquettes et des nombres, le zéro étant réservé à epsilon.

Exemple: fichier symboles.lab:

a 1
b 2
toto 3

Fichier automate: exemple-2.txt

0 1 a
0 2 b
1 2 b
1 1 a
2 2 toto
2

Voici comment on procède pour compiler et dessiner cet automate:

fsmcompile -i symboles.lab exemple-2.txt > exemple-2.fsm
fsmdraw -i symboles.lab exemple-2.fsm | dot -Tgif > exemple-2.gif

Et voici le graphique: