Automata
A finite automaton is a 5-tuple A = (Q, V, T, I, F) where :
- Q is a finite non empty set of states,
- V is a finite non empty set of inputs,
- T is a subset of QxVxQ, called set of transitions,
- I is a non empty subset of Q, called set of initial states,
- F is a subset of Q called set of final states.
A word w = w1,w2, .., wn on V is said accepted by A iff it exists a path p = p0,p1,p2,...,pn from a state i of I to a state f of F where
each pi is a state of Q, p0 = i, pn = f, and for each i, it exists a transition t = (pi-1, wi, pi) in T.
An automaton is said determinist iff
- I is a singleton,
- for each triplet (s1, x, s2) in QxVxQ, it exists at most one transition (s1, x, s2) in T.
An automaton is generally represented using a directed grph. States are
the vertices of the graph. The transitions are represented by directed
labeled edges, using the corresponding label from V. Inital states are
indicated by an incoming arrow on the state and final states by an
outgoing arrow. The following figure represents the automaton A = (Q =
{1, 2, 3}, V = {a, b}, T = {(1,a,1), (1,b,2), (2,a,3), (3,a,2),(3,b1)},
I = {1}, F = {1,2}}. The word abab is recognized by A, but not the word aba (3 is not final) or abb (there is no transition from state 2 with label b).

We consider the interfaces State and Transition and the class DeterministAutomaton.
Part 1 : Finite State Automaton
- Complete the class DeterministAutomaton with the methods :
- public State initialState()
which return the initial state of the automaton
- public Transition transition(State s, Object label)
which returns the transition of source s and label label if it exists, null otherwise. If the state s does not belong to the automaton, the method will thrown a java.lang.NoSuchElementException.
- public boolean recognize(Object [] word) and
public boolean recognize(Iterator<Object> word)
which returns if a word is recognize by the automaton
- Add an handle in the methods recognize which allows to modify the behavior of that methods by inheritance when the current state changes.
- Modify the class in such a way that DeterministicAutomaton(Transition[] transitions) throws an exception
- NotDeterministTransitionException
if two elements of transitions have the same source and the same label,
- NotDeterministInitalStateException
if among the states source or target of a transition in transitions, it exists more than one initial state,
- UnknownInitialStateException
if among the states source or target of a transition in transitions, none of them is an initial state.
Remark : the exceptions may be thrown either in the constructor or in the method addState(State e).
- Add the classes of the exceptions.
- Add two classes StateImpl and TransitionImpl which implement respectively State and Transition. The instances of those two classes will be unmodifiable and the datas will be given to the constructors.
- Add a test class.
- Modify the code in order to make generic the type of the labels
in the transitions. For exemple, the new prototype of the method label() in the interface Transition will become public T label().
The goals of the parts 2 and 3 are similar : allowing to add an action
when a transition is used during a word recognition. We will propose
two different way to answer this goal, without changing the code produced in the part 1. Moreover, the new classes will not be in the same package than the classes of part 1.
Part 2 : Observable Automaton
We want to create a class ObservableAutomaton
in order to have a class of automata which will notify attached
observers each time a transition is used during a word recognition. All
the classes of this part will be in a new package observable, except the test which will be in the default package.
- Look at the documentation of the class java.util.Observable, especially the method setChanged(). What is the problem ?
- In order to solve this problem, we will use the following solution :
- the class ObservableAutomaton inherits only from DeterministAutomaton ;
- we add an internal static class in ObservableAutomaton which extends Observable and where the method notifyObservers(Object arg) is changed by invoking the method setChanged() before the notification ; each instance of ObservableAutomaton will use an instance of this internal class as variable ;
- we add a method addObserver(Observer o) to ObservableAutomaton which attach an observer to the automaton ;
- Create a class implemeting Observer
which print on the standard output the label of the crossed transition.
Use it in the test class to write the recognized word on the standard
output.
Part 3 : Finite State Machine
In this part, we will use an interface Action<T>. All the classes of this part will be in a new package machine, except the test which will be in the default package.
- Write a class TransitionWithAction<T> which implements Transition<T> and associates a transition t and an action a. t and a are given at the construction. The methods of Transition to implement will been done by delegation to t. Moreover, TransitionWithAction implements a method State cross() which executes the action a with the label of t as argument, and returns the target of t.
- Write a class FiniteStateMachine<T> which extends DeterministAutomaton and which uses instances of TransitionWithAction as transitions. When a transition of an instance of FiniteStateMachine is used during the recognition of a word, then the method cross() on this transition is invoked.
- Create a class implementing Action<T> which print a String on the standard output. Use it in the test class to write the recognized word on the standard output.
Conclusion
Compare the two solutions of part 2 and 3.