POA - TD2 : Automates

Un automate d'états fini est un 5-uplet A = (Q, V, T, I, F) où :
Un mot w = w1,w2, .., wn sur V est dit reconnu par A si et seulement si il existe un chemin p = p0, p1, p2, ... , pn reliant un état initial i de I à un état terminal f de F, où chaque pj est un état de Q, p0 = i, pn = f et pour tout j entre 1 et n, il existe une transition t = (pj-1, wj, pj) dans T.

Un automate est dit déterministe si et seulement si
Un automate déterministe est généralement représenté par un graphe orienté. Les états sont les sommets du graphe. Les transitions sont représentées par des arcs étiquetés par le symbole de V correspondant. Les états initiaux sont indiqués par une flèche entrante et les états terminaux par une flèche sortante. La figure suivante représente l'automate A = (Q = {1, 2, 3}, V = {a, b}, T = {(1, a, 1), (1, b, 2), (2, a, 3), (3, a, 2),(3, b, 1)}, I = {1}, F = {1,2}}. Le mot abab est reconnu par A. Le mot aba n'est pas reconnu : l'état 3 n'est pas terminal, ni le mot abb : il n'existe pas de transition étiquetée b sortant de l'état 2.

 an automaton

On considère les interfaces State et Transition et la classe DeterministicAutomaton.

Partie 1 : Automate d'états fini

  1. Compléter la classe DeterministicAutomaton en rajoutant les méthodes :
  2. Modifier la classe de façon à ce que le constructeur DeterministicAutomaton(Transition[] transitions) lève une exception
  3. Remarque : les exceptions peuvent être levées directement dans le constructeur ou dans la méthode addState(State e).
  4. Donner le code des exceptions.
  5. Ajouter deux classes StateImpl et TransitionImpl qui implémentent respectivement State et Transition. Les instances de ces deux classes seront non modifiables et les données nécessaires seront fournies à la construction.
  6. Ajouter une classe de test.
  7. Modifier le code de façon à rendre générique le type des étiquettes dans les transitions. Par exemple, le nouveau prototype de la méthode label() dans l'interface Transition sera public T label().
Le but des parties 2 et 3 est similaire : permettre d'associer une action quand une transition est parcourue durant la reconnaissance d'un mot. Les deux parties correspondent à deux approches différentes pour répondre à ce besoin, sans changer le code déjà produit dans la partie 1. De plus, les nouvelles classes seront situées dans un paquetage différent de celui des classes de la partie 1.

Partie 2 : Automate Observable

On veut créer une classe ObservableAutomaton dans le but d'avoir une classe d'automate qui notifiera à des observateurs préalablement enrgistrés chaque franchissement d'une transition lors de la reconnaissance d'un mot. Toutes les classes de cette partie seront situées dans un nouveau paquetage observable, à l'exception du test situé dans le paquetage par défaut.
  1. Regarder la documentation de la classe java.util.Observable, plus spécialement la méthode setChanged(). Quel problème cela vous pose-t-il ?
  2. Dans le but de résoudre cette difficulté, utiliser la solution suivante :
  3. Créer une classe implémentant l'interface java.util.Observer qui imprime sur la sortie standard l'étiquette de la transition parcourue. Utiliser cette classe dans une classe de test affichant le mot reconnu sur la sortie standard.

Partie 3 : Machine d'états finie

Dans cette partie, on utilisera l'interface Action<T>. Toutes les classes de cette partie feront partie d'un nouveau paquetage machine, à l'exception du test situé dans le paquetage par défaut.
  1. Ecrire une classe TransitionWithAction<T> qui implémente Transition<T> et associe une transition t et une action a. t et a seront données à la construction. Les méthodes de Transition seront implémentées par délégation à t. De plus,  TransitionWithAction implémente une méthode State cross() qui exécute l'action a avec l'étiquette de t comme argument, et renvoie la destination de t.
  2. Ecrire une classe FiniteStateMachine<T> qui étend DeterministicAutomaton et qui utilise des instances de TransitionWithAction comme transitions. Quand une transition d'une instance de FiniteStateMachine est utilisée lors de la reconnaissance d'un mot, la méthode cross() de cette transition est invoquée.
  3. Créer une classe implémentant Action<T> qui imprime un objet String sur la sortie standard. Utiliser cette classe dans une classe de test pour imprimer le mot reconnu sur la sortie standard.

Conclusion

Comparer les deux solutions des parties 2 et 3.