Struct redfa::dfa::Dfa

source ·

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

Expand description

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.

Implementations§

source §

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

source

pub 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.

Examples found in repository ?

examples/test.rs (line 16)

fn main() {
    let stdin = std::io::stdin();
    for line in stdin.lock().lines() {
        let line = line.unwrap();
        match line.trim().parse::<Regex<char>>() {
            Err(e) => println!("error: {}", e),
            Ok(x) => {
                println!("ok: {:?}", x);
                let x = x.normalize();
                println!("{:?}", x);
                println!("{:?}", x.derivative().map(Normalize::normalize));
                let (dfa, _mapping) = Dfa::from_derivatives(vec![x, Regex::Null]);
                let dfa = dfa.map(|reg| reg.nullable());
                println!("DFA: {:?}\n", dfa);
                let mdfa = dfa.minimize().map(|x| *x);
                println!("Minimized DFA: {:?}\n", mdfa);
                println!("dfa == mdfa: {:?}\n", dfa == mdfa);
            }
        }
    }
}

source

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

Apply a function to each state’s value.

Examples found in repository ?

examples/test.rs (line 17)

fn main() {
    let stdin = std::io::stdin();
    for line in stdin.lock().lines() {
        let line = line.unwrap();
        match line.trim().parse::<Regex<char>>() {
            Err(e) => println!("error: {}", e),
            Ok(x) => {
                println!("ok: {:?}", x);
                let x = x.normalize();
                println!("{:?}", x);
                println!("{:?}", x.derivative().map(Normalize::normalize));
                let (dfa, _mapping) = Dfa::from_derivatives(vec![x, Regex::Null]);
                let dfa = dfa.map(|reg| reg.nullable());
                println!("DFA: {:?}\n", dfa);
                let mdfa = dfa.minimize().map(|x| *x);
                println!("Minimized DFA: {:?}\n", mdfa);
                println!("dfa == mdfa: {:?}\n", dfa == mdfa);
            }
        }
    }
}

source

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

Find the reverse transitions from each state in the DFA.

source

pub 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.

Examples found in repository ?

examples/test.rs (line 19)

fn main() {
    let stdin = std::io::stdin();
    for line in stdin.lock().lines() {
        let line = line.unwrap();
        match line.trim().parse::<Regex<char>>() {
            Err(e) => println!("error: {}", e),
            Ok(x) => {
                println!("ok: {:?}", x);
                let x = x.normalize();
                println!("{:?}", x);
                println!("{:?}", x.derivative().map(Normalize::normalize));
                let (dfa, _mapping) = Dfa::from_derivatives(vec![x, Regex::Null]);
                let dfa = dfa.map(|reg| reg.nullable());
                println!("DFA: {:?}\n", dfa);
                let mdfa = dfa.minimize().map(|x| *x);
                println!("Minimized DFA: {:?}\n", mdfa);
                println!("dfa == mdfa: {:?}\n", dfa == mdfa);
            }
        }
    }
}