automata_core 0.2.0

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

use std::collections::HashSet;
use std::hash::Hash;

use crate::arbitrary::Automaton;
use crate::arbitrary::DeterministicAutomaton;
use crate::finite::DeterministicFiniteAutomaton;
use crate::finite::FiniteAutomaton;
use crate::labeled::simple::SimpleLabeledDFA;

use super::SimpleBuildError;
use super::state::SimpleDFAState;

/// [`SimpleLabeledDFA`](crate::labeled::simple::SimpleLabeledDFA) with `Label = ()`.
///
/// Dense `usize` states and `char` alphabet; accepting states are given explicitly
/// in constructors (stored as unit labels).
pub type SimpleDFA = SimpleLabeledDFA<()>;

impl SimpleDFA {
    /// Construct a `SimpleDFA` without validating invariants.
    ///
    /// This constructor is intended for internal use and tests. It assumes:
    /// - `initial < state_count`
    /// - accepting states are within `0..state_count`
    /// - all transition endpoints are within range
    /// - transition symbols belong to `alphabet`
    /// - at most one transition per `(state, symbol)`
    pub fn new_unchecked(
        state_count: usize,
        initial: SimpleDFAState,
        accepting: impl IntoIterator<Item = SimpleDFAState>,
        alphabet: impl IntoIterator<Item = char>,
        transitions: impl IntoIterator<Item = (SimpleDFAState, char, SimpleDFAState)>,
    ) -> Self {
        let labels = accepting.into_iter().map(|s| (s, ()));
        SimpleLabeledDFA::new_labeled_unchecked(state_count, initial, labels, alphabet, transitions)
    }

    /// Construct a `SimpleDFA` with validation.
    ///
    /// See [`SimpleBuildError`] for possible failures.
    pub fn try_new(
        state_count: usize,
        initial: SimpleDFAState,
        accepting: impl IntoIterator<Item = SimpleDFAState>,
        alphabet: impl IntoIterator<Item = char>,
        transitions: impl IntoIterator<Item = (SimpleDFAState, char, SimpleDFAState)>,
    ) -> Result<Self, SimpleBuildError> {
        let labels = accepting.into_iter().map(|s| (s, ()));
        SimpleLabeledDFA::try_new_labeled(state_count, initial, labels, alphabet, transitions)
    }

    /// Same graph and acceptance, but every accepting state gets the given `label`.
    pub fn label_all_accepting_states_with<Label: Hash + Eq + Clone>(
        &self,
        label: Label,
    ) -> SimpleLabeledDFA<Label> {
        self.map_labels(|_| label.clone())
    }
}

impl Automaton for SimpleDFA {
    fn is_accepting_state(&self, state: Self::State) -> bool {
        self.labels.contains_key(&state)
    }
}

impl FiniteAutomaton for SimpleDFA {
    fn accepting_states_set(&self) -> HashSet<Self::State> {
        self.labels.keys().copied().collect()
    }
}

impl DeterministicAutomaton for SimpleDFA {}

impl DeterministicFiniteAutomaton for SimpleDFA {}