org.metasyntactic.math.automata
Class DeterministicFiniteAutomata

java.lang.Object
  |
  +--org.metasyntactic.math.automata.AbstractFiniteAutomata
        |
        +--org.metasyntactic.math.automata.NondeterministicFiniteAutomata
              |
              +--org.metasyntactic.math.automata.DeterministicFiniteAutomata
All Implemented Interfaces:
FiniteAutomata, java.io.Serializable

public class DeterministicFiniteAutomata
extends NondeterministicFiniteAutomata

FORMAL DEFINITION OF A DETERMINISTIC FINITE AUTOMATON

A finite automaton is a 5-tuple (Q, Σ, δ, q0, F) where

  1. Q is a finite set of states,
  2. Σ is a finite alphabet,
  3. δ:Q x Σε→Q is the transition function,
  4. q0∈Q is the start state, and
  5. F⊆Q is the set of accept states

See Also:
Serialized Form

Nested Class Summary
 
Nested classes inherited from class org.metasyntactic.math.automata.NondeterministicFiniteAutomata
NondeterministicFiniteAutomata.DFAState
 
Field Summary
 
Fields inherited from class org.metasyntactic.math.automata.AbstractFiniteAutomata
acceptStates, alphabet, cachedTable, decision, immedateDecisionPossible, startState, states, transitionFunction
 
Constructor Summary
DeterministicFiniteAutomata(java.util.Set states, java.util.Set alphabet, TransitionFunction transitionFunction, java.lang.Object startState, java.util.Set acceptStates)
          Constructs a new DeterministicFiniteAutomata.
 
Method Summary
 boolean accept(java.util.Iterator iterator)
          Let M = (Q, Σ, δ, q0, F) be a finite automata and w = w1w2…wn be a string over the alphabet Σ.
static boolean equivalent(DeterministicFiniteAutomata d1, DeterministicFiniteAutomata d2)
           
protected  void init()
           
 DeterministicFiniteAutomata minimizeStates()
           
 DeterministicFiniteAutomata minimizeStates(boolean compress)
          Minimizes the number of states in this DFA to the smallest number possible.
 DeterministicFiniteAutomata toDeterministicFiniteAutomata(boolean compress)
          Converts this NFA to a DFA using the 'subset construction method'
 
Methods inherited from class org.metasyntactic.math.automata.NondeterministicFiniteAutomata
accept, eClosure, eClosure, move, toDeterministicFiniteAutomata
 
Methods inherited from class org.metasyntactic.math.automata.AbstractFiniteAutomata
getAcceptStates, getAlphabet, getStartState, getStates, getTransitionFunction, toStateTable, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

DeterministicFiniteAutomata

public DeterministicFiniteAutomata(java.util.Set states,
                                   java.util.Set alphabet,
                                   TransitionFunction transitionFunction,
                                   java.lang.Object startState,
                                   java.util.Set acceptStates)
Constructs a new DeterministicFiniteAutomata.

Parameters:
states - Q is a finite set of states
alphabet - Σ is a finite alphabet
transitionFunction - δ:Q x Σε→Q is the transition function
acceptStates - F⊆Q is the set of accept states
Method Detail

init

protected void init()
Overrides:
init in class NondeterministicFiniteAutomata

accept

public boolean accept(java.util.Iterator iterator)
Let M = (Q, Σ, δ, q0, F) be a finite automata and w = w1w2…wn be a string over the alphabet Σ. The M accepts w if a sequence of states r0, r1, …, rn exists in Q with the following three conditions:
  1. r0 = q0
  2. δ(ri, wi+1) = ri+1 for i = 0, …, n - 1
  3. rn ∈ F
Condition 1 says that the machine starts in the start state. Condition 2 says that the machine goes from state to state according to the transition function. Condition 3 says that the machine accepts if it ends up in an accept state. We say that M recognizes language A if A = {w | M accepts w}.

Specified by:
accept in interface FiniteAutomata
Overrides:
accept in class NondeterministicFiniteAutomata
Parameters:
iterator - A string over some alphabet Σ
Returns:
true if this machine accepts w

equivalent

public static boolean equivalent(DeterministicFiniteAutomata d1,
                                 DeterministicFiniteAutomata d2)

minimizeStates

public DeterministicFiniteAutomata minimizeStates()

minimizeStates

public DeterministicFiniteAutomata minimizeStates(boolean compress)
Minimizes the number of states in this DFA to the smallest number possible. This DFA is then returned. compress is used to convert this dfa to one with the smallest memory footprint possible. All references to states/edges/etc. in the old DFA will be forgotten. With the addition of equivalent, setting compress to true is the preffered way to call this method.


toDeterministicFiniteAutomata

public DeterministicFiniteAutomata toDeterministicFiniteAutomata(boolean compress)
Description copied from class: NondeterministicFiniteAutomata
Converts this NFA to a DFA using the 'subset construction method'

Overrides:
toDeterministicFiniteAutomata in class NondeterministicFiniteAutomata
Parameters:
compress - Increases computation time required to construc the DFA but returns a DFA using less memory
Returns:
the DFA equivalent of this NFA