Automates Non-déterministes
1 La Reconnaissance
Reprenons la représentation introduite au premier TD :
type ('a,'b) automate = { init : 'a list ;
term : 'a list ; trans : ('a * 'b * 'a) list};;
Elle permet de représenter sans problème les automates
non-déterministes qui peuvent avoir plusieurs états initiaux et des
transitions multiples avec le même état de départ et la même
lettre. Par contre, les e-transitions ne sont pas possibles
avec cette définition de type.
L'avantage de reprendre la même définition est que toutes les
fonctions écrites lors du TD 1 continuent à fonctionner sur un
automate non-déternimiste, sauf la reconnaissance car la fonction
image suppose que l'automate est déterministe.
Pour vérifier si un mot est reconnu par un automate non-déterministe,
il faut explorer les différents chemins possibles. Ceci est facile à
faire en maintenant non pas l'état courant lors de la lecture du mot
mais l'ensemble des états possibles.
On voit donc qu'il suffit de réécrire la fonction image.
Question 1
Ecrire une fonction qui calcule l'image d'un ensemble d'états par une lettre
:
image: ('a,'b) automate -> 'a list -> 'b -> 'a list
On fera en sorte que les 'a list soient ordonnées de manière à
assurer l'égalité des ensembles (utile par la suite pour émonder et
déterminiser)
Question 2
Ecrire un interprète. Il prendra en argument l'automate et la liste de symboles
restant à lire. Il renverra un booléen indiquant si le mot est accepté ou non.
reconnait : ('a,'b) automate -> 'b list -> bool
Pour utilser cette fonction, on utilisera encore une fois la fonction
string_to_list donnée au TD 1.
2 Emondons les automates
2
Définition 1
Soit A un automate. Un état q de A est accessible
s'il existe dans A un chemin partant d'un état initial et
arrivant en q. L'état q est co-accessible s'il existe un
chemin de A partant de q et arrivant à un état final.
Définition 2
Un automate A est accessible si tous ses états sont
accessibles. Il est co-accessible si tous ses états sont
co-accessibles. Il est émondé s'il est accessible et co-accessible.
Dans un automate, seuls les états accessibles et co-accessibles
sont utiles.
Soient A l'automate
(Q, T, I, F ) (Q est l'ensemble des états, T l'ensemble des
transitions, I l'ensemble des états initiaux et F l'ensemble
des états finaux) et (Qn) la suite :
ì
ï
í
ï
î |
|
|
Q0 |
= |
I |
|
Qn+1 |
= |
| Qn È |
|
|
{q' Î Q
| (q, a, q')
Î T}
|
|
|
|
|
Question 3
Soit Qacc l'ensemble des états accessibles. Montrer qu'il
existe un entier N, tel que n³ N implique
Qn=Qacc. On voit donc qu'il suffit de calculer les Qn
jusqu'à ce que deux Qn successifs soient égaux pour obtenir Qacc.
Ecrire une fonction qui prend en
argument une liste de transitions et une liste d'états initiaux,
et renvoie la liste des états accessibles. On fera en sorte que
les 'a list soient ordonnées de manière à s'assurer que
l'égalité des ensembles corresponde à l'égalité des listes, ce qui permet
de tester facilement l'égalité des Qn.
accessibles : ('a * 'b * 'a) list -> 'a list -> 'a list
Question 4
S'inspirer de la question précédente pour proposer un algorithme
qui calcule l'ensemble des états co-accessibles d'un automate.
Ecrire une fonction qui prend en argument une liste de transitions et
une liste d'états finaux, et renvoie la liste des états co-accessibles.
coaccessibles : ('a * 'b * 'a) list -> 'a list -> 'a list
Question 5
Ecrire une fonction qui prend en argument un automate et renvoie
son émondé.
3 Les e-transitions
Dans certains cas, il est utile d'ajouter un type particulier de transition
qui ``reconnaissent'' le mot vide e.
Question 6
A partir du type automate, créer un type automate_e
permettant de coder les e-transitions.
Question 7
A partir de la fonction image, créer une fonction image_e
prennant en compte les e-transitions :
image_e: ('a,'b) automate_e -> 'a list -> 'b -> 'a list
Question 8
Montrer que l'on peut enlever les e-transitions dans un automate
non-déterministe (c'est à dire obtenir un automate non-déterministe sans
e-transitions qui reconnait le même language)
et écrire la fonction réalisant cette opération.
ote_e: ('a,'b) automate_e -> ('a,'b) automate
- 1
- C'est la même chose que dans le TD 1, le fait que l'automate ne
soit pas déterministe ne change rien au fonctionnement. Ceux qui ont déjà
écrit les fonctions vérifiront qu'elles fonctionnent toujours
- 2
- C'est la même chose que dans le TD 1, le fait que l'automate ne
soit pas déterministe ne change rien au fonctionnement. Ceux qui ont déjà
écrit les fonctions vérifiront qu'elles fonctionnent toujours
This document was translated from LATEX by HEVEA.