gregex_logic/
nfa.rs

1//! Has the implementation of a non-deterministic finite automaton (NFA).
2
3use crate::translation::setterminal::SetTerminal;
4use core::panic;
5use std::collections::{HashMap, HashSet};
6
7/// The `NFA` struct represents a non-deterministic finite automaton.
8#[derive(Debug, Default)]
9pub struct NFA {
10    /// Set of all possible states of the NFA.
11    states: HashSet<u32>,
12    /// Set of all accepting states. If the NFA ends at any one if these the simulation is succesful.
13    accept: HashSet<u32>,
14    /// The transition function is a map from a pair of a state and a character to a set of states.
15    transition_function: HashMap<(u32, char), HashSet<u32>>,
16}
17
18impl NFA {
19    /// Simulates the NFA with the given input.
20    pub fn run(&self, input: &str) -> bool {
21        let mut current_states = HashSet::new();
22        current_states.insert(0);
23        for c in input.chars() {
24            let mut next_states = HashSet::new();
25            for state in current_states {
26                if let Some(states) = self.transition_function.get(&(state, c)) {
27                    next_states.extend(states);
28                }
29            }
30            current_states = next_states;
31        }
32        !current_states.is_disjoint(&self.accept)
33    }
34
35    /// Converts the prefix, suffix and factors sets to a NFA.
36    pub fn set_to_nfa(
37        prefix_set: &HashSet<SetTerminal>,
38        suffix_set: &HashSet<SetTerminal>,
39        factors_set: &HashSet<SetTerminal>,
40    ) -> Self {
41        let mut nfa = Self::default();
42    
43        for i in prefix_set {
44            match *i {
45                SetTerminal::SingleElement(symbol, index) => {
46                    nfa.states.insert(index);
47                    nfa.transition_function
48                        .insert((0, symbol), vec![index].into_iter().collect());
49                }
50                SetTerminal::DoubleElement(_, _, _, _) => {
51                    panic!("DoubleElement not supported")
52                }
53                _ => {}
54            }
55        }
56    
57        for i in suffix_set {
58            match *i {
59                SetTerminal::SingleElement(_, index) => {
60                    nfa.states.insert(index);
61                    nfa.accept.insert(index);
62                }
63                SetTerminal::DoubleElement(_, _, _, _) => {
64                    panic!("DoubleElement not supported")
65                }
66                _ => {}
67            }
68        }
69    
70        for i in factors_set {
71            match *i {
72                SetTerminal::DoubleElement(_, index1, symbol2, index2) => {
73                    nfa.states.insert(index1);
74                    nfa.states.insert(index2);
75                    nfa.transition_function.entry((index1, symbol2)).or_insert_with(HashSet::new).insert(index2);
76                }
77                SetTerminal::SingleElement(_, _) => {
78                    panic!("SingleElement not supported")
79                }
80                _ => {}
81            }
82        }
83    
84        nfa
85    }
86}
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    #[test]
93    fn simulate_nfa_simple_test() {
94        let nfa = NFA {
95            states: vec![0, 1, 2].into_iter().collect(),
96            accept: vec![2].into_iter().collect(),
97            transition_function: vec![
98                ((0, 'a'), vec![0, 1].into_iter().collect()),
99                ((1, 'b'), vec![2].into_iter().collect()),
100            ]
101            .into_iter()
102            .collect(),
103        };
104        assert!(nfa.run("ab"));
105    }
106
107    #[test]
108    fn set_to_nfa_simple_test() {
109        let prefix_set = vec![SetTerminal::SingleElement('a', 1)].into_iter().collect();
110        let suffix_set = vec![SetTerminal::SingleElement('b', 2)].into_iter().collect();
111        let factors_set = vec![SetTerminal::DoubleElement('a', 1, 'b', 2)].into_iter().collect();
112        let nfa = NFA::set_to_nfa(&prefix_set, &suffix_set, &factors_set);
113        assert!(nfa.run("ab"));
114    }
115}
gregex_logic/nfa.rs

gregex_logic/
nfa.rs
