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