automata_core 0.2.1

Deterministic and nondeterministic automata algorithms in Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

use automata_core::{
    finite::NonDeterministicFiniteAutomaton,
    labeled::{
        arbitrary::{DeterministicLabeledAutomaton, LabeledAutomaton},
        finite::{DeterministicFiniteLabeledAutomaton, NonDeterministicFiniteLabeledAutomaton},
        simple::SimpleLabeledDFA,
    },
    simple::SimpleNFA,
};

////////////////////////////////////////////////////////////
// Helpers
////////////////////////////////////////////////////////////

fn nfa_singleton(words: &str) -> SimpleNFA {
    let alphabet = words.chars();
    let symbols = words.chars();
    SimpleNFA::try_new_singleton_words(alphabet, symbols).unwrap()
}

fn nfa_a_plus() -> SimpleNFA {
    let a = nfa_singleton("a");
    a.concatenate(&a.star())
}

fn nfa_letter() -> SimpleNFA {
    let letter = nfa_singleton("abcdefghijklmnopqrstuvwxyz");
    letter
}

fn nfa_ident() -> SimpleNFA {
    let letter = nfa_letter();
    letter.concatenate(&letter.star())
}

fn ldfa_ident_or_a_plus() -> SimpleLabeledDFA<u8> {
    let ident = nfa_ident().label_all_accepting_states_with(0u8);
    let a_plus = nfa_a_plus().label_all_accepting_states_with(1u8);
    let lnfa = ident.union(&a_plus);
    lnfa.to_dfa_by(Ord::min).minimize()
}

fn ldfa_a_plus_or_ident() -> SimpleLabeledDFA<u8> {
    let ident = nfa_ident().label_all_accepting_states_with(1u8);
    let a_plus = nfa_a_plus().label_all_accepting_states_with(0u8);
    let lnfa = ident.union(&a_plus);
    lnfa.to_dfa_by(Ord::min).minimize()
}

////////////////////////////////////////////////////////////
// Tests
////////////////////////////////////////////////////////////

#[test]
fn ldfa_ident_or_a_plus_state_set_is_correct() {
    let ldfa = ldfa_ident_or_a_plus();
    let states_count = ldfa.states().count();
    assert_eq!(states_count, 2);
}

#[test]
fn ldfa_a_plus_or_ident_state_set_is_correct() {
    let ldfa = ldfa_a_plus_or_ident();
    let states_count = ldfa.states().count();
    assert_eq!(states_count, 3);
}

#[test]
fn ldfa_ident_or_a_plus_state_set_labels_are_correct() {
    let ldfa = ldfa_ident_or_a_plus();
    let label_of_aa = ldfa.get_label_of_word(&['a', 'a']);
    let label_of_bb = ldfa.get_label_of_word(&['b', 'b']);
    assert_eq!(label_of_aa, Some(0u8));
    assert_eq!(label_of_bb, Some(0u8));
}

#[test]
fn ldfa_a_plus_or_ident_state_set_labels_are_correct() {
    let ldfa = ldfa_a_plus_or_ident();
    let label_of_aa = ldfa.get_label_of_word(&['a', 'a']);
    let label_of_bb = ldfa.get_label_of_word(&['b', 'b']);
    assert_eq!(label_of_aa, Some(0u8));
    assert_eq!(label_of_bb, Some(1u8));
}

#[test]
fn ldfa_drop_labels() {
    let ldfa = ldfa_ident_or_a_plus();
    let ldfa_dropped_labels = ldfa.drop_labels();
    assert_eq!(ldfa_dropped_labels.get_label_of_word(&['a', 'b']), Some(()));
}