Automata

A finite automaton is a 5-tuple A = (Q, V, T, I, F) where :
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 deterministic iff
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).

 an automaton

We consider the interfaces State and Transition and the class DeterministicAutomaton.

Part 1 : Finite State Automaton

  1. Complete the class DeterministicAutomaton with the new methods :
  2. Modify the class in such a way that DeterministicAutomaton(Transition[] transitions) throws an exception
  3. Add the classes of the exceptions.
  4. 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.
  5. Add a test class.
  6. 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.
  1. Look at the documentation of the class java.util.Observable, especially the method setChanged(). What is the problem ?
  2. In order to solve this problem, we will use the following solution :
  3. 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.
  1. 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.
  2. 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.
  3. 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.