Struct redfa::dfa::Dfa

pub struct Dfa<T, V> {
    pub states: Vec<State<T, V>>,
}

A deterministic finite automaton (DFA), over the alphabet T. Each state is annotated with a value of type V. State 0 is the starting state.

Fields

states: Vec<State<T, V>>

The list of states.

Methods

impl<T, V> Dfa<T, V>

fn from_derivatives(initial: Vec<V>) -> (Dfa<T, V>, BTreeMap<V, u32>) where
    T: Ord,
    V: Differentiable<T> + Normalize + Ord + Clone, 

Construct a DFA from a list of differentiable objects. The elements of initial form the first states of the DFA. Returns the DFA, together with a mapping from derivatives to state numbers.

fn map<U, F>(self, f: F) -> Dfa<T, U> where
    F: FnMut(V) -> U, 

Apply a function to each state's value.

fn reverse(&self) -> Vec<(BTreeMap<&T, BTreeSet<usize>>, BTreeSet<usize>)> where
    T: Ord, 

Find the reverse transitions from each state in the DFA.

fn minimize(&self) -> Dfa<T, &V> where
    T: Ord + Clone,
    V: Ord, 

Minimize a DFA; i.e. find a DFA with the fewest states that is equivalent to the given DFA. Two DFAs are equivalent if, given the same string, they always lead to a state with the same associated value.

impl<T, V> Dfa<T, V>

fn equiv<U>(&self, other: &Dfa<T, U>) -> bool where
    T: Ord + Clone,
    U: Ord,
    V: Ord + PartialEq<U>, 

Compare DFAs by language equality.

Trait Implementations

impl<T: Debug, V: Debug> Debug for Dfa<T, V>

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T: Clone, V: Clone> Clone for Dfa<T, V>

fn clone(&self) -> Dfa<T, V>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Ord, U, V: PartialEq<U>> PartialEq<Dfa<T, U>> for Dfa<T, V>

Compare DFAs by graph isomorphism.

fn eq(&self, other: &Dfa<T, U>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<T: Ord, V: Eq> Eq for Dfa<T, V>