finite_automata/
enfa.rs

1use std::{
2    collections::{
3        BTreeMap as Map,
4        BTreeSet as Set,
5    },
6    iter,
7};
8use ::segment_map::{
9    Segment,
10    SegmentMap,
11    segment_map,
12};
13use crate::{
14    StateIndex,
15    TransitionIndex,
16    Subsume,
17    Nfa,
18    Dfa,
19    StatesContains,
20    StatesIndex,
21    StatesSlice,
22    states_contains_from,
23};
24
25/// A nondeterministic finite automaton with epsilon moves.
26#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
27pub struct Enfa<S, T> {
28    state_to_index: Map<S, StateIndex>,
29    index_to_state: Map<StateIndex, S>,
30    next_state_index: u128,
31    transition_to_index: Map<StateIndex, SegmentMap<T, Map<StateIndex, TransitionIndex>>>,
32    index_to_transition: Map<TransitionIndex, (StateIndex, Segment<T>, StateIndex)>,
33    next_transition_index: u128,
34    initial_index: StateIndex,
35    final_indices: Set<StateIndex>
36}
37
38impl<S: Clone + Ord, T: Clone + Ord> Enfa<S, T> {
39    /// Create a new nondeterministic finite automaton with epsilon moves with the given initial state.
40    pub fn new(initial: S) -> Enfa<S, T> {
41        Enfa {
42            state_to_index: map![initial.clone() => 0.into()],
43            index_to_state: map![0.into() => initial],
44            next_state_index: 1,
45            transition_to_index: Map::new(),
46            index_to_transition: Map::new(),
47            next_transition_index: 0,
48            initial_index: 0.into(),
49            final_indices: Set::new(),
50        }
51    }
52
53    /// Insert the state and return the associated state index.
54    pub fn states_insert(&mut self, state: S) -> StateIndex {
55        if let Some(&state_index) = self.state_to_index.get(&state) {
56            state_index
57        } else {
58            let state_index = self.next_state_index.into();
59            self.next_state_index += 1;
60            self.state_to_index.insert(state.clone(), state_index);
61            self.index_to_state.insert(state_index, state);
62            state_index
63        }
64    }
65}
66
67impl<S: Ord, T: Ord> Enfa<S, T> {
68    /// Return the state index of the state, if it exists.
69    pub fn states_contains(&self, state: &S) -> Option<StateIndex> {
70        self.state_to_index.get(state).copied()
71    }
72
73    /// Get the state at the state index.
74    pub fn states_index(&self, state_index: StateIndex) -> &S {
75        self.index_to_state.get(&state_index).expect("state index out of bounds")
76    }
77
78    /// Convert the state indices to states.
79    pub fn states_slice<'a>(&'a self, state_indices: impl IntoIterator<Item = StateIndex> + 'a) -> Box<dyn Iterator<Item = &S> + 'a> {
80        Box::new(state_indices.into_iter().map(move |state_index| self.states_index(state_index)))
81    }
82
83    /// Get all the state indices.
84    pub fn state_indices<'a>(&'a self) -> Box<dyn Iterator<Item = StateIndex> + 'a> {
85        Box::new(self.index_to_state.keys().copied())
86    }
87
88    /// Get all the state indices for the states within the epsilon closure around the state index.
89    pub fn closure_indices<'a>(&'a self, state_index: StateIndex) -> Box<dyn Iterator<Item = StateIndex> + 'a> {
90        let mut stack = vec![state_index];
91        let mut closure = Set::new();
92        while let Some(source_index) = stack.pop() {
93            closure.insert(source_index);
94            for transition_index in self.transition_indices_from(source_index) {
95                let (_, transition_segment, target_index) = self.transitions_index(transition_index);
96                if transition_segment.is_empty() {
97                    if !closure.contains(&target_index) {
98                        stack.push(target_index);
99                    }
100                }
101            }
102        }
103        let result = Box::new(closure.into_iter());
104        result
105    }
106}
107
108impl<S: Clone + Ord, T: Clone + Ord> Enfa<S, T> {
109    /// Insert the transition and return the associated transition index.
110    pub fn transitions_insert(&mut self, transition: (StateIndex, Segment<T>, StateIndex)) -> TransitionIndex {
111        let (source_index, transition_segment, target_index) = transition;
112        if self.index_to_state.get(&source_index).is_none() {
113            panic!("source state index out of bounds");
114        }
115        if self.index_to_state.get(&target_index).is_none() {
116            panic!("target state index out of bounds");
117        }
118        let transition_index = self.next_transition_index.into();
119        self.next_transition_index += 1;
120        if let Some(transitions) = self.transition_to_index.get_mut(&source_index) {
121            transitions.update(&transition_segment, |targets| {
122                if let Some(mut targets) = targets {
123                    if targets.get(&target_index).is_some() {
124                        panic!("transition segments must not overlap");
125                    }
126                    targets.insert(target_index, transition_index);
127                    Some(targets)
128                } else {
129                    Some(map![target_index => transition_index])
130                }
131            });
132        } else {
133            self.transition_to_index.insert(source_index, segment_map![transition_segment.clone() => map![target_index => transition_index]]);
134        }
135        self.index_to_transition.insert(transition_index, (source_index, transition_segment, target_index));
136        transition_index
137    }
138}
139
140impl<S: Ord, T: Ord> Enfa<S, T> {
141    /// Return the transition index of the transition, if it exists.
142    pub fn transitions_contains(&self, transition: (StateIndex, &T, StateIndex)) -> Option<TransitionIndex> {
143        let (source_index, transition, target_index) = transition;
144        self.transition_to_index.get(&source_index).and_then(|transitions| transitions.get(transition).and_then(|targets| targets.get(&target_index))).copied()
145    }
146
147    /// Get the transition at the transition index.
148    pub fn transitions_index(&self, transition_index: TransitionIndex) -> (StateIndex, &Segment<T>, StateIndex) {
149        let (source_index, transition, target_index) = self.index_to_transition.get(&transition_index).expect("transition index out of bounds");
150        (*source_index, transition, *target_index)
151    }
152
153    /// Convert the transition indices to transitions.
154    pub fn transitions_slice<'a>(&'a self, transition_indices: impl IntoIterator<Item = TransitionIndex> + 'a) -> Box<dyn Iterator<Item = (StateIndex, &Segment<T>, StateIndex)> + 'a> {
155        Box::new(transition_indices.into_iter().map(move |transition_index| self.transitions_index(transition_index)))
156    }
157
158    /// Get all the transition indices.
159    pub fn transition_indices<'a>(&'a self) -> Box<dyn Iterator<Item = TransitionIndex> + 'a> {
160        Box::new(self.index_to_transition.keys().copied())
161    }
162
163    /// Get the transition indices originating at the state index.
164    pub fn transition_indices_from<'a>(&'a self, state_index: StateIndex) -> Box<dyn Iterator<Item = TransitionIndex> + 'a> {
165        if self.index_to_state.get(&state_index).is_none() {
166            panic!("state index out of bounds");
167        }
168        if let Some(transitions_from) = self.transition_to_index.get(&state_index) {
169            Box::new(transitions_from.iter().flat_map(|(_, targets_from)| targets_from.iter().map(|(_, transition_index_from)| transition_index_from)).copied())
170        } else {
171            Box::new(iter::empty())
172        }
173    }
174
175    /// Get the index of the initial state.
176    pub fn initial_index(&self) -> StateIndex {
177        self.initial_index
178    }
179
180    /// Check if the state at the state index is a final state.
181    pub fn is_final(&self, state_index: StateIndex) -> bool {
182        self.final_indices.contains(&state_index)
183    }
184    
185    /// Set the state at the state index as a final state.
186    pub fn set_final(&mut self, state_index: StateIndex) {
187        self.final_indices.insert(state_index);
188    }
189
190    /// Get all the state indices for final states.
191    pub fn final_indices<'a>(&'a self) -> Box<dyn Iterator<Item = StateIndex> + 'a> {
192        Box::new(self.final_indices.iter().copied())
193    }
194}
195
196impl<S: Clone + Ord, T: Clone + Ord> From<&Nfa<S, T>> for Enfa<S, T> {
197    /// Create a new nondeterministic finite automaton with epsilon moves from the nondeterministic finite automaton.
198    fn from(nfa: &Nfa<S, T>) -> Enfa<S, T> {
199        let initial = nfa.states_index(nfa.initial_index());
200        let mut enfa = Enfa::new(initial.clone());
201        for state_index in nfa.state_indices() {
202            let state = nfa.states_index(state_index);
203            enfa.states_insert(state.clone());
204        }
205        for transition_index in nfa.transition_indices() {
206            let (source_index, transition, target_index) = nfa.transitions_index(transition_index);
207            let source_index = states_contains_from(&enfa, nfa, source_index).expect("state does not exist");
208            let target_index = states_contains_from(&enfa, nfa, target_index).expect("state does not exist");
209            enfa.transitions_insert((source_index, transition.clone(), target_index));
210        }
211        for final_index in nfa.final_indices() {
212            let final_index = states_contains_from(&enfa, nfa, final_index).expect("state does not exist");
213            enfa.set_final(final_index);
214        }
215        enfa
216    }
217}
218
219impl<S: Clone + Ord, T: Clone + Ord> From<&Dfa<S, T>> for Enfa<S, T> {
220    /// Create a new nondeterministic finite automaton with epsilon moves from the deterministic finite automaton.
221    fn from(dfa: &Dfa<S, T>) -> Enfa<S, T> {
222        let initial = dfa.states_index(dfa.initial_index());
223        let mut enfa = Enfa::new(initial.clone());
224        for state_index in dfa.state_indices() {
225            let state = dfa.states_index(state_index);
226            enfa.states_insert(state.clone());
227        }
228        for transition_index in dfa.transition_indices() {
229            let (source_index, transition, target_index) = dfa.transitions_index(transition_index);
230            let source_index = states_contains_from(&enfa, dfa, source_index).expect("state does not exist");
231            let target_index = states_contains_from(&enfa, dfa, target_index).expect("state does not exist");
232            enfa.transitions_insert((source_index, transition.clone(), target_index));
233        }
234        for final_index in dfa.final_indices() {
235            let final_index = states_contains_from(&enfa, dfa, final_index).expect("state does not exist");
236            enfa.set_final(final_index);
237        }
238        enfa
239    }
240}
241
242impl<S: Clone + Ord, T: Clone + Ord> Subsume<Enfa<S, T>> for Enfa<S, T> {
243    /// Insert all the states and transitions of the nondeterministic finite automaton with epsilon moves.
244    fn subsume(&mut self, enfa: &Enfa<S, T>) {
245        for state_index in enfa.state_indices() {
246            let state = enfa.states_index(state_index);
247            self.states_insert(state.clone());
248        }
249        for transition_index in enfa.transition_indices() {
250            let (source_index, transition, target_index) = enfa.transitions_index(transition_index);
251            let source_index = states_contains_from(self, enfa, source_index).expect("state does not exist");
252            let target_index = states_contains_from(self, enfa, target_index).expect("state does not exist");
253            self.transitions_insert((source_index, transition.clone(), target_index));
254        }
255    }
256}
257
258impl<S: Clone + Ord, T: Clone + Ord> Subsume<Nfa<S, T>> for Enfa<S, T> {
259    /// Insert all the states and transitions of the nondeterministic finite automaton.
260    fn subsume(&mut self, nfa: &Nfa<S, T>) {
261        for state_index in nfa.state_indices() {
262            let state = nfa.states_index(state_index);
263            self.states_insert(state.clone());
264        }
265        for transition_index in nfa.transition_indices() {
266            let (source_index, transition, target_index) = nfa.transitions_index(transition_index);
267            let source_index = states_contains_from(self, nfa, source_index).expect("state does not exist");
268            let target_index = states_contains_from(self, nfa, target_index).expect("state does not exist");
269            self.transitions_insert((source_index, transition.clone(), target_index));
270        }
271    }
272}
273
274impl<S: Clone + Ord, T: Clone + Ord> Subsume<Dfa<S, T>> for Enfa<S, T> {
275    /// Insert all the states and transitions of the deterministic finite automaton.
276    fn subsume(&mut self, dfa: &Dfa<S, T>) {
277        for state_index in dfa.state_indices() {
278            let state = dfa.states_index(state_index);
279            self.states_insert(state.clone());
280        }
281        for transition_index in dfa.transition_indices() {
282            let (source_index, transition, target_index) = dfa.transitions_index(transition_index);
283            let source_index = states_contains_from(self, dfa, source_index).expect("state does not exist");
284            let target_index = states_contains_from(self, dfa, target_index).expect("state does not exist");
285            self.transitions_insert((source_index, transition.clone(), target_index));
286        }
287    }
288}
289
290impl<S: Ord, T: Ord> StatesContains<S> for Enfa<S, T> {
291    fn states_contains(&self, state: &S) -> Option<StateIndex> {
292        self.states_contains(state)
293    }
294}
295
296impl<S: Ord, T: Ord> StatesIndex<S> for Enfa<S, T> {
297    fn states_index(&self, state_index: StateIndex) -> &S {
298        self.states_index(state_index)
299    }
300}
301
302impl<S: Ord, T: Ord> StatesSlice<S> for Enfa<S, T> {
303    fn states_slice<'a>(&'a self, state_indices: impl IntoIterator<Item = StateIndex> + 'a) -> Box<dyn Iterator<Item = &S> + 'a> {
304        self.states_slice(state_indices)
305    }
306}
307
308#[cfg(test)]
309mod tests {
310    use std::{
311        collections::BTreeSet as Set,
312        fmt::Debug,
313    };
314    use segment_map::Segment;
315    use crate::Enfa;
316
317    #[test]
318    fn test_epsilon() {
319        let expected = Expected::<_, i32> {
320            initial: 0,
321            transitions: set![
322                (0, Segment::empty(), 1)
323            ],
324            finals: set![1]
325        };
326        let mut actual = Enfa::new(0);
327        let s0 = actual.initial_index();
328        let s1 = actual.states_insert(1);
329        actual.transitions_insert((s0, Segment::empty(), s1));
330        actual.set_final(s1);
331        assert_eq(expected, actual);
332    }
333
334    #[test]
335    fn test_symbol() {
336        let expected = Expected {
337            initial: 0,
338            transitions: set![
339                (0, Segment::singleton(A), 1)
340            ],
341            finals: set![1]
342        };
343        let mut actual = Enfa::new(0);
344        let s0 = actual.initial_index();
345        let s1 = actual.states_insert(1);
346        actual.transitions_insert((s0, Segment::singleton(A), s1));
347        actual.set_final(s1);
348        assert_eq(expected, actual);
349    }
350
351    #[test]
352    fn test_alternation() {
353        let expected = Expected {
354            initial: 0,
355            transitions: set![
356                (0, Segment::empty(), 2),
357                (0, Segment::empty(), 4),
358                (2, Segment::empty(), 3),
359                (4, Segment::singleton(A), 5),
360                (3, Segment::empty(), 1),
361                (5, Segment::empty(), 1)
362            ],
363            finals: set![1]
364        };
365        let mut actual = Enfa::new(0);
366        let s0 = actual.initial_index();
367        let s1 = actual.states_insert(1);
368        let s2 = actual.states_insert(2);
369        let s3 = actual.states_insert(3);
370        let s4 = actual.states_insert(4);
371        let s5 = actual.states_insert(5);
372        actual.transitions_insert((s0, Segment::empty(), s2));
373        actual.transitions_insert((s0, Segment::empty(), s4));
374        actual.transitions_insert((s2, Segment::empty(), s3));
375        actual.transitions_insert((s4, Segment::singleton(A), s5));
376        actual.transitions_insert((s3, Segment::empty(), s1));
377        actual.transitions_insert((s5, Segment::empty(), s1));
378        actual.set_final(s1);
379        assert_eq(expected, actual);
380    }
381
382    #[test]
383    fn test_concatenation() {
384        let expected = Expected {
385            initial: 0,
386            transitions: set![
387                (0, Segment::empty(), 2),
388                (2, Segment::singleton(A), 3),
389                (3, Segment::empty(), 4),
390                (4, Segment::empty(), 5),
391                (5, Segment::empty(), 1)
392            ],
393            finals: set![1]
394        };
395        let mut actual = Enfa::new(0);
396        let s0 = actual.initial_index();
397        let s1 = actual.states_insert(1);
398        let s2 = actual.states_insert(2);
399        let s3 = actual.states_insert(3);
400        let s4 = actual.states_insert(4);
401        let s5 = actual.states_insert(5);
402        actual.transitions_insert((s0, Segment::empty(), s2));
403        actual.transitions_insert((s2, Segment::singleton(A), s3));
404        actual.transitions_insert((s3, Segment::empty(), s4));
405        actual.transitions_insert((s4, Segment::empty(), s5));
406        actual.transitions_insert((s5, Segment::empty(), s1));
407        actual.set_final(s1);
408        assert_eq(expected, actual);
409    }
410
411    #[test]
412    fn test_repetition() {
413        let expected = Expected {
414            initial: 0,
415            transitions: set![
416                (0, Segment::empty(), 1),
417                (0, Segment::empty(), 2),
418                (2, Segment::singleton(A), 3),
419                (3, Segment::empty(), 2),
420                (3, Segment::empty(), 1)
421            ],
422            finals: set![1]
423        };
424        let mut actual = Enfa::new(0);
425        let s0 = actual.initial_index();
426        let s1 = actual.states_insert(1);
427        let s2 = actual.states_insert(2);
428        let s3 = actual.states_insert(3);
429        actual.transitions_insert((s0, Segment::empty(), s1));
430        actual.transitions_insert((s0, Segment::empty(), s2));
431        actual.transitions_insert((s2, Segment::singleton(A), s3));
432        actual.transitions_insert((s3, Segment::empty(), s2));
433        actual.transitions_insert((s3, Segment::empty(), s1));
434        actual.set_final(s1);
435        assert_eq(expected, actual);
436    }
437
438    struct Expected<S, T> {
439        initial: S,
440        transitions: Set<(S, Segment<T>, S)>,
441        finals: Set<S>,
442    }
443
444    fn assert_eq<S: Clone + Debug + Ord, T: Clone + Debug + Ord>(expected: Expected<S, T>, actual: Enfa<S, T>) {
445        assert_eq!(expected.initial, actual.states_index(actual.initial_index()).clone(), "initial");
446        assert_eq!(expected.transitions, actual.transitions_slice(actual.transition_indices()).map(|(source, transition, target)| (actual.states_index(source).clone(), transition.clone(), actual.states_index(target).clone())).collect(), "transitions");
447        assert_eq!(expected.finals, actual.states_slice(actual.final_indices()).cloned().collect(), "finals");
448    }
449
450    static A: i32 = 0;
451}
finite_automata/enfa.rs

finite_automata/
enfa.rs
