automata_core 0.1.2

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
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
92
93
94
95
96

use crate::finite::automaton::FiniteAutomaton;
use crate::finite::deterministic::DeterministicFiniteAutomaton;
use crate::general::NonDeterministicAutomaton;

/// Finite nondeterministic automata operations.
///
/// This trait adds finite-alphabet combinators and classical closure
/// operations for NFAs (union/intersection/concatenation/star, etc.),
/// together with determinization.
pub trait NonDeterministicFiniteAutomaton: NonDeterministicAutomaton + FiniteAutomaton {
    /// Deterministic representation obtained by determinization.
    type CorrespondingDFA: DeterministicFiniteAutomaton<State = Self::State, Input = Self::Input, CorrespondingNFA = Self>;

    /// Determinize this NFA into a DFA (subset construction).
    fn to_dfa(&self) -> Self::CorrespondingDFA;

    /// Language union: `L(self) ∪ L(other)`.
    fn union(&self, other: &Self) -> Self;
    /// Language difference: `L(self) \ L(other)`.
    fn difference(&self, other: &Self) -> Self;
    /// Concatenation: `L(self) · L(other)`.
    fn concatenate(&self, other: &Self) -> Self;
    /// Intersection: `L(self) ∩ L(other)`.
    fn intersection(&self, other: &Self) -> Self;

    /// Kleene star (0 or more repetitions).
    fn star(&self) -> Self;
    /// Reverse all transitions and swap initial/final roles.
    fn reverse(&self) -> Self;

    /// Trim to `accessible ∩ co_accessible`.
    fn trimmed(&self) -> Self;
    /// Complement language.
    ///
    /// Typically requires a total DFA completion pipeline internally.
    fn complement(&self) -> Self;

    /// Restrict to `reachable` states.
    fn accessible(&self) -> Self;
    /// Restrict to `co-reachable` states.
    fn co_accessible(&self) -> Self;

    /// Check whether `L(self) ⊆ L(other)`.
    fn is_subset_of(&self, other: &Self) -> bool;
    /// Check whether `L(self) = L(other)`.
    fn is_equivalent_to(&self, other: &Self) -> bool;

    /// Whether the recognized language is empty.
    fn is_empty_language(&self) -> bool {
        !self.reachable_states().iter().any(|&s| self.is_accepting_state(s))
    }

    /// Language union across many NFAs.
    ///
    /// Computes `L(a0) ∪ L(a1) ∪ ...` for every automaton produced by `automata`.
    ///
    /// Returns `None` if the slice is empty.
    fn union_all(automata: &[Self]) -> Option<Self>
        where Self: Clone + Sized
    {
        clone_reduce(automata, |a, b| a.union(b))
    }
    
    /// Concatenation across many NFAs.
    ///
    /// Computes `L(a0) · L(a1) · ...` in iteration order.
    ///
    /// Returns `None` if the slice is empty.
    fn concatenate_all(automata: &[Self]) -> Option<Self> 
        where Self: Clone + Sized 
    {
        clone_reduce(automata, |a, b| a.concatenate(b))
    }
    
    /// Language intersection across many NFAs.
    ///
    /// Computes `L(a0) ∩ L(a1) ∩ ...` for every automaton produced by `automata`.
    ///
    /// Returns `None` if the slice is empty.
    fn intersect_all(automata: &[Self]) -> Option<Self> 
        where Self: Clone + Sized 
    {
        clone_reduce(automata, |a, b| a.intersection(b))
    }
}

fn clone_reduce<'a, T: Clone>(arr: &[T], f: impl Fn(T, &T) -> T) -> Option<T> {
    let mut iter = arr.iter();

    let Some(item) = iter.next() else {
        return None;
    };

    Some(iter.fold(item.clone(), |a, b| f(a, &b)))
}