cz.cuni.mff.ksi.jinfer.base.automaton
Class Automaton<T>

java.lang.Object
  cz.cuni.mff.ksi.jinfer.base.automaton.Automaton<T>

Direct Known Subclasses:

DefectiveAutomaton, RegexpAutomaton

public class Automaton<T>
extends Object

Class representing deterministic finite automaton. Can simplify itself when given mergingCondition Automaton can be non-deterministic for algorithmic reasons. Of course, there is no constraint that each state has to have transition on each symbol. But what more, there can be multiple transitions from one step on same symbol, pointing to different states (real non-determinism) or to same state (just non-canonical form). When merging occurs, this deviations can appear. Non-canonical form, when there are two-or-more steps on same symbol between two states, is solved (and collapsed to only one step) automatically by merging procedure. Non-deterministic form is not solved by automaton itself. The merging algorithm has to deal with this opportunity is it gives bad order of merging states. But it can let it non-deterministic by design.

Field Summary

protected Map<State<T>,Set<Step<T>>>	delta Transition function of automaton.
protected State<T>	initialState Initial state of automaton, entry point.
protected Map<State<T>,State<T>>	mergedStates Merged states - when state X is merged into state Y, we say, X is being merged out (from automaton).
protected Map<Integer,State<T>>	nameMap TODO anti comment
protected int	newStateName New state name is an integer that is assigned to any new state created by createNewState.
protected Map<State<T>,Set<Step<T>>>	reverseDelta Transition function of automaton, mathematically the same as delta.
protected Map<State<T>,Set<State<T>>>	reverseMergedStates As in mergedStates, but in opposing direction.

Constructor Summary

Automaton()
Constructor which doesn't create initialState

Automaton(Automaton<T> anotherAutomaton)

Automaton(boolean createInitialState)

Method Summary

void	buildPTAOnRegexp(Regexp<T> regexp)
void	buildPTAOnSymbol(List<T> symbolString) Given symbolString, iterates through it and follows steps in automaton.
protected State<T>	createNewState() Creates new state and return it.
Map<State<T>,Set<Step<T>>>	getDelta()
State<T>	getInitialState()
Map<State<T>,State<T>>	getMergedStates()
protected Integer	getNewStateName()
Step<T>	getOutStepOnSymbol(State<T> state, T symbol) Returns first step from state, which accepts given symbol.
protected State<T>	getRealState(State<T> state)
Map<State<T>,Set<Step<T>>>	getReverseDelta()
Map<State<T>,Set<State<T>>>	getReverseMergedStates()
void	mergeStates(List<State<T>> lst)
void	mergeStates(State<T> _mainState, State<T> _mergedState)
String	toString()
String	toTestString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

initialState

protected State<T> initialState

Initial state of automaton, entry point. State in which automaton is when starting reading input. Has to be in delta function keySet. Has no incoming steps.

delta

protected final Map<State<T>,Set<Step<T>>> delta

Transition function of automaton. Maps states to their outgoing steps. KeySet is a set of all states of automaton. State is removed by delta.remove(state) and reverseDelta.remove(state)

reverseDelta

protected final Map<State<T>,Set<Step<T>>> reverseDelta

Transition function of automaton, mathematically the same as delta. For programmatic reasons we have the reverse map, state mapping to ist incoming steps. Loops are therefore findable by using delta and reverseDelta so be careful when counting loops - may count twice.

newStateName

protected int newStateName

New state name is an integer that is assigned to any new state created by createNewState. It is always incremented in createNewState so no two states share same name. Numbers freed by state removing are not used again, sequence only grows.

mergedStates

protected final Map<State<T>,State<T>> mergedStates

Merged states - when state X is merged into state Y, we say, X is being merged out (from automaton). Because simplification may require us to merge state X again with another state (using old name of state), we need to remember for each merged out state the destination state. That's what this map is used for, for every merged out state X (merging into Y), entry (X, Y) is added into map. As state can be merged out at most once, using map is all-right for this purpose. When request to merge state X arrives at future, and X is no longer in delta function, the real (correct) state to merge will be searched using this map.

reverseMergedStates

protected final Map<State<T>,Set<State<T>>> reverseMergedStates

As in mergedStates, but in opposing direction. Holds information about all the states, that merged to "key" in map. When X merges into Y, this is done: reverseMergedStates.get(Y).add(X)

nameMap

protected final Map<Integer,State<T>> nameMap

TODO anti comment

Constructor Detail

Automaton

public Automaton()

Constructor which doesn't create initialState

Automaton

public Automaton(boolean createInitialState)

Parameters:

createInitialState - - true= create initial state, false- as default constructor

Automaton

public Automaton(Automaton<T> anotherAutomaton)

Method Detail

createNewState

protected final State<T> createNewState()

Creates new state and return it. This is preferred way to extend automaton states. It initializes delta map, and revesre delta map with empty linkedhashsets of steps, increments newstatename. Process of extending automaton is therefore: 1. create state using this function 2. create steps giving them proper sources,destinations 3. put step instances correctly in delta map and reverseDelta map.

Returns:

getOutStepOnSymbol

public Step<T> getOutStepOnSymbol(State<T> state,
                                  T symbol)

Returns first step from state, which accepts given symbol. If there are multiple such steps, return only one found.

Parameters:

state -

symbol -

Returns:

buildPTAOnSymbol

public void buildPTAOnSymbol(List<T> symbolString)

Given symbolString, iterates through it and follows steps in automaton. When there isn't a step to follow, new state and step is created. Resulting in tree-formed automaton.

Parameters:

symbolString - - list of symbols (one word from accepting language)

buildPTAOnRegexp

public void buildPTAOnRegexp(Regexp<T> regexp)

getRealState

protected State<T> getRealState(State<T> state)

mergeStates

public void mergeStates(List<State<T>> lst)

mergeStates

public void mergeStates(State<T> _mainState,
                        State<T> _mergedState)

toString

public String toString()

Overrides:

toString in class Object

toTestString

public String toTestString()

getInitialState

public State<T> getInitialState()

Returns:

the initialState

getDelta

public Map<State<T>,Set<Step<T>>> getDelta()

Returns:

the delta

getReverseDelta

public Map<State<T>,Set<Step<T>>> getReverseDelta()

Returns:

the reverseDelta

getNewStateName

protected Integer getNewStateName()

Returns:

the newStateName

getMergedStates

public Map<State<T>,State<T>> getMergedStates()

Returns:

the mergedStates

getReverseMergedStates

public Map<State<T>,Set<State<T>>> getReverseMergedStates()

Returns:

the reverseMergedStates