deterministic_finite_automaton/
lib.rs

1use std::collections::HashSet;
2use std::hash::Hash;
3
4pub struct DFA<StateType, AlphabetType> {
5    states: HashSet<StateType>,
6    alphabet: HashSet<AlphabetType>,
7    transition: Box<dyn Fn(StateType, AlphabetType) -> StateType>,
8    start: StateType,
9    accept: HashSet<StateType>,
10}
11
12#[derive(Clone, Copy, Debug, PartialEq)]
13pub enum Status<S> {
14    Accept(S),
15    Reject(S),
16}
17
18impl<S, A> DFA<S, A>
19where
20    S: Eq + Hash + Clone,
21    A: Eq + Hash + Clone,
22{
23    pub fn new(
24        states: impl IntoIterator<Item = S>,
25        alphabet: impl IntoIterator<Item = A>,
26        transition: impl Fn(S, A) -> S + 'static,
27        start: S,
28        accept: impl IntoIterator<Item = S>,
29    ) -> DFA<S, A> {
30        DFA {
31            states: HashSet::from_iter(states.into_iter()),
32            alphabet: HashSet::from_iter(alphabet.into_iter()),
33            transition: Box::new(transition),
34            start,
35            accept: HashSet::from_iter(accept.into_iter()),
36        }
37    }
38
39    pub fn states(&self) -> &HashSet<S> {
40        &self.states
41    }
42
43    pub fn alphabet(&self) -> &HashSet<A> {
44        &self.alphabet
45    }
46
47    pub fn transition_function(&self) -> &Box<dyn Fn(S, A) -> S> {
48        &self.transition
49    }
50
51    pub fn start_state(&self) -> &S {
52        &self.start
53    }
54
55    pub fn accept_states(&self) -> &HashSet<S> {
56        &self.accept
57    }
58
59    pub fn input(&self, s: impl IntoIterator<Item = A>) -> Status<S> {
60        let mut state = self.start.clone();
61
62        for c in s.into_iter() {
63            state = (self.transition)(state, c);
64        }
65
66        if self.accept.contains(&state) {
67            Status::Accept(state)
68        } else {
69            Status::Reject(state)
70        }
71    }
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn it_works() {
80        let result = 2 + 2;
81        assert_eq!(result, 4);
82    }
83
84    #[test]
85    fn create_dfa() {
86        let dfa = DFA::new(
87            [1, 2, 3],
88            ['a', 'b'],
89            |state, input| match (state, input) {
90                (1, 'a') => 2,
91                _ => 3,
92            },
93            1,
94            [2],
95        );
96
97        assert!(dfa.states() == &HashSet::from([1, 2, 3]));
98        assert!(dfa.alphabet() == &HashSet::from(['a', 'b']));
99        assert!(*dfa.start_state() == 1);
100        assert!(dfa.accept_states() == &HashSet::from([2]));
101    }
102
103    #[test]
104    fn run_inputs() {
105        let dfa = DFA::new(
106            [0, 1, 2],
107            ['0', '1'],
108            |state, input| match (state, input) {
109                (0, '0') => 0,
110                (0, '1') => 1,
111                (1, '0') => 2,
112                (1, '1') => 0,
113                (2, '0') => 1,
114                (2, '1') => 2,
115                _ => panic!("invalid state"),
116            },
117            0,
118            [0],
119        );
120
121        assert!(dfa.input("0".chars()) == Status::Accept(0));
122        assert!(dfa.input("1".chars()) == Status::Reject(1));
123        assert!(dfa.input("11".chars()) == Status::Accept(0));
124        assert!(dfa.input("10".chars()) == Status::Reject(2));
125        assert!(dfa.input("1001".chars()) == Status::Accept(0));
126    }
127}
deterministic_finite_automaton/lib.rs

deterministic_finite_automaton/
lib.rs
