org.metasyntactic.math.automata
Class TransitionFunction

java.lang.Object
  |
  +--org.metasyntactic.math.automata.TransitionFunction
All Implemented Interfaces:
java.io.Serializable

public class TransitionFunction
extends java.lang.Object
implements java.io.Serializable

We use something clled a transition function, frequently denoted δ, to define the rules for moving. If the finite automaton has an arrow from a state x to a state y labeled with input symbol 1, that means that, if the automaton is in state x when it reads a 1, it then moves to state y. We can indicate the same thing with the transition function by saying that δ(x,1)=y. This notation is a kind of mathematical shorthand.

See Also:
Serialized Form

Field Summary
protected  java.util.Map inputToOutput
           
 
Constructor Summary
TransitionFunction()
          Creates an empty transition function table
TransitionFunction(TransitionFunction tf)
          Creates a copy of this Transition function
 
Method Summary
 void addAllFunctions(TransitionFunction tf)
          Add all functions contained in tf into this
 void addFunction(java.lang.Object state, java.util.List symbols, java.lang.Object output)
          Adds a function to this table in the form of: initialState X symbol → finalState
 void clear()
          Removes all functions from this transition function
 boolean containsFunction(java.lang.Object state, java.util.List symbols, java.lang.Object output)
           
 boolean equals(java.lang.Object o)
           
 boolean equals(TransitionFunction tf)
           
 java.util.List getSymbols(java.lang.Object state, java.lang.Object output)
           
 int hashCode()
           
 java.lang.Object operate(java.lang.Object state, java.util.List symbols)
          Returns the result that these two objects map to If this doesn't map to any Object then an Empty Set is returned
 java.util.Set reachableStates(java.lang.Object state)
          Returns the set of directly connected outputs to this state
 void replace(java.util.Map oldStateToNew)
          In a transition of a X b → c, if a or c are contained in oldStateToNew, they will be replaced with the new state they map to
 void retainAll(java.util.Set states)
          Keeps all functions that include any Object in states as the startstate
 int size()
           
 java.lang.String toString()
           
 java.lang.Object[][] toTable()
          Returns a table representing this transition function.
 java.lang.Object[][] toTable(java.util.Set states)
           
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

inputToOutput

protected final java.util.Map inputToOutput
Constructor Detail

TransitionFunction

public TransitionFunction()
Creates an empty transition function table


TransitionFunction

public TransitionFunction(TransitionFunction tf)
Creates a copy of this Transition function

Parameters:
tf - The transition function to make a copy of
Method Detail

addFunction

public void addFunction(java.lang.Object state,
                        java.util.List symbols,
                        java.lang.Object output)
Adds a function to this table in the form of: initialState X symbol → finalState


addAllFunctions

public void addAllFunctions(TransitionFunction tf)
Add all functions contained in tf into this


containsFunction

public boolean containsFunction(java.lang.Object state,
                                java.util.List symbols,
                                java.lang.Object output)

retainAll

public void retainAll(java.util.Set states)
Keeps all functions that include any Object in states as the startstate


clear

public void clear()
Removes all functions from this transition function


operate

public final java.lang.Object operate(java.lang.Object state,
                                      java.util.List symbols)
Returns the result that these two objects map to If this doesn't map to any Object then an Empty Set is returned

Returns:
state x symbol → returnVal

reachableStates

public java.util.Set reachableStates(java.lang.Object state)
Returns the set of directly connected outputs to this state


replace

public void replace(java.util.Map oldStateToNew)
In a transition of a X b → c, if a or c are contained in oldStateToNew, they will be replaced with the new state they map to


getSymbols

public java.util.List getSymbols(java.lang.Object state,
                                 java.lang.Object output)

hashCode

public int hashCode()
Overrides:
hashCode in class java.lang.Object

size

public int size()

equals

public boolean equals(TransitionFunction tf)

equals

public boolean equals(java.lang.Object o)
Overrides:
equals in class java.lang.Object

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

toTable

public java.lang.Object[][] toTable(java.util.Set states)

toTable

public java.lang.Object[][] toTable()
Returns a table representing this transition function. in the form:
    symbols
  s
  t
  a
  t
  e
  s
 

The contents of the table are thusly: {for all d(q1, a) = q2 | q1 & q2 ∈ Q & a ∈ Σ}: The element at q1 x a is q2, otherwise it is null. The special case is at 0,0 where the empty string is placed