Class DFA

java.lang.Object
  DFA

public class DFA
extends Object

Java implementation of deterministic finite state automata.

A trap state is implicit; that is, any unspecified transition is treated as ending in a trap state from which there is no exit.

The transition function is represented as a Map of Maps. The outer map associates a state with its state-specific transition function subset (a transition table row) which is itself represented as a mapping from input symbol to destination state.

Note that unspecified cases have undefined results.

Version:

CSTheory (4)

Author:

Dr. Jody Paul

Constructor Summary

DFA(Set<State> states, Set<String> alphabet, Map<State,Map<String,State>> transition, State start, Set<State> accept)
Fully parameterized constructor for DFA objects.

Method Summary

boolean	accepts(String input) Determines whether given string is accepted or rejected by this DFA.
Set<State>	acceptStates() Retrieves the set of accept states.
Set<String>	alphabet() Retrieves the alphabet of this DFA.
State	initialState() Retrieves the initial state of this DFA, if any.
State	nextState(State source, String input) Lookup transition for specified state and input.
Set<State>	states() Retrieves the set of all states.
Map<State,Map<String,State>>	transitionFunction() Retrieves the transition function of this DFA.

Methods inherited from class java.lang.Object

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

Constructor Detail

DFA

public DFA(Set<State> states,
           Set<String> alphabet,
           Map<State,Map<String,State>> transition,
           State start,
           Set<State> accept)

Fully parameterized constructor for DFA objects.

Parameters:

states - the set of states of this DFA

alphabet - the alphabet of this DFA

transition - the transition function of this DFA

start - the start state of this DFA

accept - the set of accept states of this DFA

Method Detail

accepts

public boolean accepts(String input)

Determines whether given string is accepted or rejected by this DFA. Each state's activity couner is initialized to zero, then incremented by one each time the state is entered.

Parameters:

input - the input string; allows both "" and null to indicate the empty string ε

Returns:

true if the string is in the language recognized by this DFA; false otherwise

acceptStates

public Set<State> acceptStates()

Retrieves the set of accept states.

Returns:

accept states

alphabet

public Set<String> alphabet()

Retrieves the alphabet of this DFA.

Returns:

the alphabet

initialState

public State initialState()

Retrieves the initial state of this DFA, if any.

Returns:

the initial state; null if none

nextState

public State nextState(State source,
                       String input)

Lookup transition for specified state and input.

Parameters:

source - the source state

input - the input symbol

Returns:

the destination state; null if none

states

public Set<State> states()

Retrieves the set of all states.

Returns:

the states

transitionFunction

public Map<State,Map<String,State>> transitionFunction()

Retrieves the transition function of this DFA.

Returns:

the transition function