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 = 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
I est un singleton,
pour tout couple (e0, s) de QxV, il existe au plus une transition (e0, s, e1) 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