POA - TD2 : Automates

Un automate d'états fini est un 5-uplet A = (Q, V, T, I, F) où :

Q est un ensemble non vide d'états,
V est un ensemble non vide de symboles, appelé alphabet,
T est un sous-ensemble de QxVxQ, appelé ensemble des transitions,
I est un sous-ensemble non vide de Q, appelé ensemble des états initiaux,
F est un sous-ensemble de Q appelé ensemble des états terminaux.

Un mot w = w₁,w₂, .., w_n sur V est dit reconnu par A si et seulement si il existe un chemin p = p₀, p₁, p₂, ... , p_n reliant un état initial i de I à un état terminal f de F, où chaque p_j est un état de Q, p₀ = i, p_n = f et pour tout j entre 1 et n, il existe une transition t = (p_j-1, w_j, p_j) dans T.

Un automate est dit déterministe si et seulement si

I est un singleton,
pour tout couple (e₀, s) de QxV, il existe au plus une transition (e₀, s, e₁) dans T.

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.

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

Partie 1 : Automate d'états fini

Compléter la classe DeterministicAutomaton en rajoutant les méthodes :

public State initialState()
qui renvoie l'état initial de l'automate
public Transition transition(State s, Object label)
qui renvoie la transition de source s et d'étiquette label si elle existe, null sinon. Si l'automate ne contient pas l'état s, la méthode lèvera une exception java.util.NoSuchElementException.
public boolean recognize(Object [] word) et
public boolean recognize(Iterator<Object> word)
qui retourne si un mot est reconnu par un automate ou non. Pour éviter la duplication de code, on utilisera l'expression Arrays.asList(a).iterator() qui renvoie un itérateur sur le tableau a.
Ajouter une "poignée" aux méthodes recognize , qui permette de modifier le comportement de ces méthodes par héritage, quand on change d'état courant lors de la reconnaissance d'un mot.

Modifier la classe de façon à ce que le constructeur DeterministicAutomaton(Transition[] transitions) lève une exception

NotDeterministicTransitionException
si deux éléments de transitions ont la même source et la même étiquette,
NotDeterministicInitalStateException
si parmi tous les états source ou cible d'une transition de transitions, il existe au moins deux états initiaux,
UnknownInitialStateException
si parmi tous les états source ou cible d'une transition de transitions, il n'existe aucun état initial.

Remarque

addState(State e)

Donner le code des exceptions.
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.
Ajouter une classe de test.
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.

Regarder la documentation de la classe java.util.Observable, plus spécialement la méthode setChanged(). Quel problème cela vous pose-t-il ?
Dans le but de résoudre cette difficulté, utiliser la solution suivante :

la classe ObservableAutomaton étend la classe DeterministicAutomaton ;
ajouter une classe interne anonyme dans ObservableAutomaton qui étend Observable et où la méthode notifyObservers(Object arg) est modifiée en invoquant la méthode setChanged() avant la notification ; chaque instance d'ObservableAutomaton utilisera comme variable une instance de cette classe interne ;
ajouter une méthode addObserver(Observer o) à ObservableAutomaton qui attache un observateur à l'automate ;

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.

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.
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.
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.