automata_core 0.1.0

Deterministic and nondeterministic finite-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

use crate::general::automaton::Automaton;

/// Deterministic automaton semantics.
///
/// Implementors provide a single `transition` function. This trait then
/// supplies [`accepts`] as a word-level convenience.
pub trait DeterministicAutomaton: Automaton {
    /// The unique initial state.
    fn initial_state(&self) -> Self::State;

    /// The deterministic step function.
    fn transition(&self, state: Self::State, input: &Self::Input) -> Option<Self::State>;

    /// Check whether the automaton accepts `word`.
    ///
    /// This default implementation repeatedly applies [`transition`] to
    /// consume the input. If at any step the transition is missing
    /// (`None`), the word is rejected.
    fn accepts(&self, word: &[Self::Input]) -> bool {
        let mut state = self.initial_state();
        for input in word {
            let Some(new_state) = self.transition(state, input) else {
                return false;
            };
            state = new_state;
        }
        self.is_accepting_state(state)
    }
}