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, Σ, δ, q₀, F) where

1. Q is a finite set of states,
2. Σ is a finite alphabet,
3. δ:Q x Σ_ε→Q is the transition function,
4. q₀∈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, Σ, δ, q₀, F) be a finite automata and w = w₁w₂…w_n be a string over the alphabet Σ. The M accepts w if a sequence of states r₀, r₁, …, r_n exists in Q with the following three conditions:

1. r₀ = q₀
2. δ(r_i, w_i+1) = r_i+1 for i = 0, …, n - 1
3. r_n ∈ 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