Dessin d'automate

Généralités

Un des objectifs de départ était de pouvoir dessiner un automate donné. Mais la tâche, en apparence assez simple, s'est révélée beaucoup plus ardue. En effet, un problème s'est très vite posé. Il concernait la minimisation des croisements de transitions. Il fallait choisir judicieusement d'une part, la position des états à l'écran et d'autre part les courbes définissant les transitions afin de minimiser ces croisements.

Une solution peut être d'analyser très profondément l'automate et ses transitions pour définir des « noyaux », c'est-à-dire rassembler les états possédant beaucoup de transitions entre eux. On peut alors s'occuper de ses « noyaux » constitués de 2 ou 3 états, les traiter de façon très poussée pour minimiser les croisements. Il suffit ensuite de les relier avec les transitions qu'ils possèdent en commun.

Définition des « noyaux » d'un automate

Ceci peut se faire encore une fois grâce à une matrice de voisinage : l'élément $v_{i,j}$ contient le nombre de liaisons qu'ils existent entre les états $i$ et $j$. Pour définir une classe, il suffit de partir d'un élément et de lui adjoindre les états ayant au moins deux transitions en communs avec lui. La matrice de voisinage étant préalablement définie, la fonction (cf. PROGRAMME 3.8) va construire la liste des classes d'un automate donné. La fonction range calcule la liste [1;...;n] et la fonction copains la liste des états possédant au moins deux transitions avec t.

PROGRAMME 3.8: Définition des « noyaux » d'un automate

Calcul de la position des états et des transitions

A partir des classes définies précédemment, on définit la position des états sur l'écran : on répartit les classes verticalement, puis chaque classe est représentée en plaçant régulièrement les états sur une horizontale.

Ensuite, pour chaque classe, les transitions sont définies en faisant varier un angle et la longueur de la tangente à la courbe de BEZIER (cf. FIGURE 3.3). La variation de l'angle est choisie pour augmenter plus rapidement au début qu'à la fin et ainsi tendre lentement vers $\pi/2$. Quand ces transitions ont été définies, il suffit de définir celles existant entre les classes.

Le résultat de la fonction sera le même que celui de la fonction de dessin d'automate, c'est-à-dire la liste des états, des transitions, des transitions instantanées, des états initiaux et des états finaux. Ceci peut permettre de pouvoir modifier ces données justement grâce à cette fonction de dessin (déplacement d'états, de transitions, ...) et donc d'améliorer le résultat, qui est souvent imparfait.

Les exemples présentés montrent ce que ce programme parvient à faire. On voit d'une part que même si certains croisements existent, le résultat est proche de ce que l'on peut faire à la main (cf. FIGURE 1.2 et FIGURE 3.4). D'autre part, ce résultat dépend beaucoup de l'automate : l'automate des MINES (cf. FIGURE 3.5) est correctement représenté alors que celui de CENTRALE (cf. FIGURE 3.6) est complètement illisible car il nécessite une représentation par arbre.

FIGURE 3.3: Pour détailler la méthode de calcul des transitions

FIGURE: L'automate de la FIGURE 1.2

FIGURE 3.5: L'automate du sujet MINES '98

FIGURE 3.6: L'automate du sujet CENTRALE '98