finite_automata/
dfa.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    Enfa,
18    Nfa,
19    StatesContains,
20    StatesIndex,
21    StatesSlice,
22    states_contains_from,
23    states_contains_closure_from,
24};
25
26/// A deterministic finite automaton.
27#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
28pub struct Dfa<S, T> {
29    state_to_index: Map<S, StateIndex>,
30    index_to_state: Map<StateIndex, S>,
31    next_state_index: u128,
32    transition_to_index: Map<StateIndex, SegmentMap<T, (StateIndex, TransitionIndex)>>,
33    index_to_transition: Map<TransitionIndex, (StateIndex, Segment<T>, StateIndex)>,
34    next_transition_index: u128,
35    initial_index: StateIndex,
36    final_indices: Set<StateIndex>
37}
38
39impl<S: Clone + Ord, T: Clone + Ord> Dfa<S, T> {
40    /// Create a new deterministic finite automaton with the given initial state.
41    pub fn new(initial: S) -> Dfa<S, T> {
42        Dfa {
43            state_to_index: map![initial.clone() => 0.into()],
44            index_to_state: map![0.into() => initial],
45            next_state_index: 1,
46            transition_to_index: Map::new(),
47            index_to_transition: Map::new(),
48            next_transition_index: 0,
49            initial_index: 0.into(),
50            final_indices: Set::new(),
51        }
52    }
53
54    /// Insert the state and return the associated state index.
55    pub fn states_insert(&mut self, state: S) -> StateIndex {
56        if let Some(&state_index) = self.state_to_index.get(&state) {
57            state_index
58        } else {
59            let state_index = self.next_state_index.into();
60            self.next_state_index += 1;
61            self.state_to_index.insert(state.clone(), state_index);
62            self.index_to_state.insert(state_index, state);
63            state_index
64        }
65    }
66}
67
68impl<S: Ord, T: Ord> Dfa<S, T> {
69    /// Return the state index of the state, if it exists.
70    pub fn states_contains(&self, state: &S) -> Option<StateIndex> {
71        self.state_to_index.get(state).copied()
72    }
73
74    /// Get the state at the state index.
75    pub fn states_index(&self, state_index: StateIndex) -> &S {
76        self.index_to_state.get(&state_index).expect("state index out of bounds")
77    }
78
79    /// Convert the state indices to states.
80    pub fn states_slice<'a>(&'a self, state_indices: impl IntoIterator<Item = StateIndex> + 'a) -> Box<dyn Iterator<Item = &S> + 'a> {
81        Box::new(state_indices.into_iter().map(move |state_index| self.states_index(state_index)))
82    }
83
84    /// Get all the state indices.
85    pub fn state_indices<'a>(&'a self) -> Box<dyn Iterator<Item = StateIndex> + 'a> {
86        Box::new(self.index_to_state.keys().copied())
87    }
88}
89
90impl<S: Clone + Ord, T: Clone + Ord> Dfa<S, T> {
91    /// Insert the transition and return the associated transition index.
92    pub fn transitions_insert(&mut self, transition: (StateIndex, Segment<T>, StateIndex)) -> TransitionIndex {
93        let (source_index, transition_segment, target_index) = transition;
94        if self.index_to_state.get(&source_index).is_none() {
95            panic!("source state index out of bounds");
96        }
97        if self.index_to_state.get(&target_index).is_none() {
98            panic!("target state index out of bounds");
99        }
100        let transition_index = self.next_transition_index.into();
101        self.next_transition_index += 1;
102        if let Some(transitions) = self.transition_to_index.get_mut(&source_index) {
103            transitions.update(&transition_segment, |target_index_transition_index| {
104                if target_index_transition_index.is_some() {
105                    panic!("transition segments must not overlap")
106                } else {
107                    Some((target_index, transition_index))
108                }
109            });
110        } else {
111            self.transition_to_index.insert(source_index, segment_map![transition_segment.clone() => (target_index, transition_index)]);
112        }
113        self.index_to_transition.insert(transition_index, (source_index, transition_segment, target_index));
114        transition_index
115    }
116}
117
118impl<S: Ord, T: Ord> Dfa<S, T> {
119    /// Return the transition index of the transition, if it exists.
120    pub fn transitions_contains(&self, transition: (StateIndex, &T, StateIndex)) -> Option<TransitionIndex> {
121        let (source_index, transition_element, target_index) = transition;
122        if let Some(target_and_index) = self.transition_to_index.get(&source_index).and_then(|transitions| transitions.get(transition_element)) {
123            if target_index == target_and_index.0 {
124                Some(target_and_index.1)
125            } else {
126                None
127            }
128        } else {
129            None
130        }
131    }
132
133    /// Return the transition index of the transition with the outgoing data, if it exists.
134    pub fn transitions_contains_outgoing(&self, transition: (StateIndex, &T)) -> Option<TransitionIndex> {
135        let (source_index, transition_element) = transition;
136        if let Some(&(_, transition_index)) = self.transition_to_index.get(&source_index).and_then(|transitions| transitions.get(transition_element)) {
137            Some(transition_index)
138        } else {
139            None
140        }
141    }
142
143    /// Get the transition at the transition index.
144    pub fn transitions_index(&self, transition_index: TransitionIndex) -> (StateIndex, &Segment<T>, StateIndex) {
145        let (source_index, transition, target_index) = self.index_to_transition.get(&transition_index).expect("transition index out of bounds");
146        (*source_index, transition, *target_index)
147    }
148
149    /// Convert the transition indices to transitions.
150    pub fn transitions_slice<'a>(&'a self, transition_indices: impl IntoIterator<Item = TransitionIndex> + 'a) -> Box<dyn Iterator<Item = (StateIndex, &Segment<T>, StateIndex)> + 'a> {
151        Box::new(transition_indices.into_iter().map(move |transition_index| self.transitions_index(transition_index)))
152    }
153
154    /// Get all the transition indices.
155    pub fn transition_indices<'a>(&'a self) -> Box<dyn Iterator<Item = TransitionIndex> + 'a> {
156        Box::new(self.index_to_transition.keys().copied())
157    }
158
159    /// Get the transition indices originating at the state index.
160    pub fn transition_indices_from<'a>(&'a self, state_index: StateIndex) -> Box<dyn Iterator<Item = TransitionIndex> + 'a> {
161        if self.index_to_state.get(&state_index).is_none() {
162            panic!("state index out of bounds");
163        }
164        if let Some(transitions_from) = self.transition_to_index.get(&state_index) {
165            Box::new(transitions_from.iter().map(|(_, (_, transition_index_from))| transition_index_from).copied())
166        } else {
167            Box::new(iter::empty())
168        }
169    }
170
171    /// Get the index of the initial state.
172    pub fn initial_index(&self) -> StateIndex {
173        self.initial_index
174    }
175
176    /// Check if the state at the state index is a final state.
177    pub fn is_final(&self, state_index: StateIndex) -> bool {
178        self.final_indices.contains(&state_index)
179    }
180    
181    /// Set the state at the state index as a final state.
182    pub fn set_final(&mut self, state_index: StateIndex) {
183        self.final_indices.insert(state_index);
184    }
185
186    /// Get all the state indices for final states.
187    pub fn final_indices<'a>(&'a self) -> Box<dyn Iterator<Item = StateIndex> + 'a> {
188        Box::new(self.final_indices.iter().copied())
189    }
190}
191
192impl<S: Clone + Ord, T: Clone + Ord> From<&Enfa<S, T>> for Dfa<Set<S>, T> {
193    /// Create a new deterministic finite automaton from the nondeterministic finite automaton with epsilon moves.
194    fn from(enfa: &Enfa<S, T>) -> Dfa<Set<S>, T> {
195        let initial_closure_indices: Set<StateIndex> = enfa.closure_indices(enfa.initial_index()).collect();
196        let initial_closure = enfa.states_slice(initial_closure_indices.iter().copied()).cloned().collect();
197        let mut stack = vec![initial_closure_indices];
198        let mut dfa = Dfa::new(initial_closure);
199        while let Some(source_closure_indices) = stack.pop() {
200            let source_index = states_contains_closure_from(&dfa, enfa, source_closure_indices.iter().copied()).expect("closure does not exist");
201            let mut target_closures_indices: SegmentMap<T, Set<StateIndex>> = SegmentMap::new();
202            for &source_closure_index in &source_closure_indices {
203                if enfa.is_final(source_closure_index) {
204                    dfa.set_final(source_index);
205                }
206                for transition_index in enfa.transition_indices_from(source_closure_index) {
207                    let (_, transition_segment, target_index) = enfa.transitions_index(transition_index);
208                    if !transition_segment.is_empty() {
209                        target_closures_indices.update(&transition_segment, |target_closure_indices| {
210                            if let Some(mut target_closure_indices) = target_closure_indices {
211                                target_closure_indices.extend(enfa.closure_indices(target_index));
212                                Some(target_closure_indices)
213                            } else {
214                                Some(enfa.closure_indices(target_index).collect())
215                            }
216                        });
217                    }
218                }
219            }
220            for (transition, target_closure_indices) in target_closures_indices {
221                if let Some(target_index) = states_contains_closure_from(&dfa, enfa, target_closure_indices.iter().copied()) {
222                    dfa.transitions_insert((source_index, transition, target_index));
223                } else {
224                    let target_closure = enfa.states_slice(target_closure_indices.iter().copied()).cloned().collect();
225                    stack.push(target_closure_indices);
226                    let target_index = dfa.states_insert(target_closure);
227                    dfa.transitions_insert((source_index, transition, target_index));
228                }
229            }
230        }
231        dfa
232    }
233}
234
235impl<S: Clone + Ord, T: Clone + Ord> From<&Nfa<S, T>> for Dfa<Set<S>, T> {
236    /// Create a new deterministic finite automaton from the nondeterministic finite automaton.
237    fn from(nfa: &Nfa<S, T>) -> Dfa<Set<S>, T> {
238        let initial_closure_indices = set![nfa.initial_index()];
239        let initial_closure = nfa.states_slice(initial_closure_indices.iter().copied()).cloned().collect();
240        let mut stack = vec![initial_closure_indices];
241        let mut dfa = Dfa::new(initial_closure);
242        while let Some(source_closure_indices) = stack.pop() {
243            let source_index = states_contains_closure_from(&dfa, nfa, source_closure_indices.iter().copied()).expect("closure does not exist");
244            let mut target_closures_indices: SegmentMap<T, Set<StateIndex>> = SegmentMap::new();
245            for &source_closure_index in &source_closure_indices {
246                if nfa.is_final(source_closure_index) {
247                    dfa.set_final(source_index);
248                }
249                for transition_index in nfa.transition_indices_from(source_closure_index) {
250                    let (_, transition_segment, target_index) = nfa.transitions_index(transition_index);
251                    target_closures_indices.update(&transition_segment, |target_closure_indices| {
252                        if let Some(mut target_closure_indices) = target_closure_indices {
253                            target_closure_indices.insert(target_index);
254                            Some(target_closure_indices)
255                        } else {
256                            Some(set![target_index])
257                        }
258                    });
259                }
260            }
261            for (transition, target_closure_indices) in target_closures_indices {
262                if let Some(target_index) = states_contains_closure_from(&dfa, nfa, target_closure_indices.iter().copied()) {
263                    dfa.transitions_insert((source_index, transition, target_index));
264                } else {
265                    let target_closure = nfa.states_slice(target_closure_indices.iter().copied()).cloned().collect();
266                    stack.push(target_closure_indices);
267                    let target_index = dfa.states_insert(target_closure);
268                    dfa.transitions_insert((source_index, transition, target_index));
269                }
270            }
271        }
272        dfa
273    }
274}
275
276impl<S: Clone + Ord, T: Clone + Ord> Subsume<Enfa<S, T>> for Dfa<Set<S>, T> {
277    /// Insert all the states and transitions of the nondeterministic finite automaton with epsilon moves.
278    fn subsume(&mut self, enfa: &Enfa<S, T>) {
279        let initial_closure_indices: Set<StateIndex> = enfa.closure_indices(enfa.initial_index()).collect();
280        let initial_closure = enfa.states_slice(initial_closure_indices.iter().copied()).cloned().collect();
281        let mut stack = vec![initial_closure_indices];
282        self.states_insert(initial_closure);
283        while let Some(source_closure_indices) = stack.pop() {
284            let source_index = states_contains_closure_from(self, enfa, source_closure_indices.iter().copied()).expect("closure does not exist");
285            let mut target_closures_indices: SegmentMap<T, Set<StateIndex>> = SegmentMap::new();
286            for &source_closure_index in &source_closure_indices {
287                if enfa.is_final(source_closure_index) {
288                    self.set_final(source_index);
289                }
290                for transition_index in enfa.transition_indices_from(source_closure_index) {
291                    let (_, transition_segment, target_index) = enfa.transitions_index(transition_index);
292                    if !transition_segment.is_empty() {
293                        target_closures_indices.update(&transition_segment, |target_closure_indices| {
294                            if let Some(mut target_closure_indices) = target_closure_indices {
295                                target_closure_indices.extend(enfa.closure_indices(target_index));
296                                Some(target_closure_indices)
297                            } else {
298                                Some(enfa.closure_indices(target_index).collect())
299                            }
300                        });
301                    }
302                }
303            }
304            for (transition, target_closure_indices) in target_closures_indices {
305                if let Some(target_index) = states_contains_closure_from(self, enfa, target_closure_indices.iter().copied()) {
306                    self.transitions_insert((source_index, transition, target_index));
307                } else {
308                    let target_closure = enfa.states_slice(target_closure_indices.iter().copied()).cloned().collect();
309                    stack.push(target_closure_indices);
310                    let target_index = self.states_insert(target_closure);
311                    self.transitions_insert((source_index, transition, target_index));
312                }
313            }
314        }
315    }
316}
317
318impl<S: Clone + Ord, T: Clone + Ord> Subsume<Nfa<S, T>> for Dfa<Set<S>, T> {
319    /// Insert all the states and transitions of the nondeterministic finite automaton.
320    fn subsume(&mut self, nfa: &Nfa<S, T>) {
321        let initial_closure_indices = set![nfa.initial_index()];
322        let initial_closure = nfa.states_slice(initial_closure_indices.iter().copied()).cloned().collect();
323        let mut stack = vec![initial_closure_indices];
324        self.states_insert(initial_closure);
325        while let Some(source_closure_indices) = stack.pop() {
326            let source_index = states_contains_closure_from(self, nfa, source_closure_indices.iter().copied()).expect("closure does not exist");
327            let mut target_closures_indices: SegmentMap<T, Set<StateIndex>> = SegmentMap::new();
328            for &source_closure_index in &source_closure_indices {
329                if nfa.is_final(source_closure_index) {
330                    self.set_final(source_index);
331                }
332                for transition_index in nfa.transition_indices_from(source_closure_index) {
333                    let (_, transition_segment, target_index) = nfa.transitions_index(transition_index);
334                    target_closures_indices.update(&transition_segment, |target_closure_indices| {
335                        if let Some(mut target_closure_indices) = target_closure_indices {
336                            target_closure_indices.insert(target_index);
337                            Some(target_closure_indices)
338                        } else {
339                            Some(set![target_index])
340                        }
341                    });
342                }
343            }
344            for (transition, target_closure_indices) in target_closures_indices {
345                if let Some(target_index) = states_contains_closure_from(self, nfa, target_closure_indices.iter().copied()) {
346                    self.transitions_insert((source_index, transition, target_index));
347                } else {
348                    let target_closure = nfa.states_slice(target_closure_indices.iter().copied()).cloned().collect();
349                    stack.push(target_closure_indices);
350                    let target_index = self.states_insert(target_closure);
351                    self.transitions_insert((source_index, transition, target_index));
352                }
353            }
354        }
355    }
356}
357
358impl<S: Clone + Ord, T: Clone + Ord> Subsume<Dfa<S, T>> for Dfa<S, T> {
359    /// Insert all the states and transitions of the deterministic finite automaton.
360    fn subsume(&mut self, dfa: &Dfa<S, T>) {
361        for state_index in dfa.state_indices() {
362            let state = dfa.states_index(state_index);
363            self.states_insert(state.clone());
364        }
365        for transition_index in dfa.transition_indices() {
366            let (source_index, transition, target_index) = dfa.transitions_index(transition_index);
367            let source_index = states_contains_from(self, dfa, source_index).expect("state does not exist");
368            let target_index = states_contains_from(self, dfa, target_index).expect("state does not exist");
369            self.transitions_insert((source_index, transition.clone().into(), target_index));
370        }
371    }
372}
373
374impl<S: Ord, T: Ord> StatesContains<S> for Dfa<S, T> {
375    fn states_contains(&self, state: &S) -> Option<StateIndex> {
376        self.states_contains(state)
377    }
378}
379impl<S: Ord, T: Ord> StatesIndex<S> for Dfa<S, T> {
380    fn states_index(&self, state_index: StateIndex) -> &S {
381        self.states_index(state_index)
382    }
383}
384
385impl<S: Ord, T: Ord> StatesSlice<S> for Dfa<S, T> {
386    fn states_slice<'a>(&'a self, state_indices: impl IntoIterator<Item = StateIndex> + 'a) -> Box<dyn Iterator<Item = &S> + 'a> {
387        self.states_slice(state_indices)
388    }
389}
390
391#[cfg(test)]
392mod tests {
393    use std::{
394        collections::BTreeSet as Set,
395        fmt::Debug,
396    };
397    use segment_map::Segment;
398    use crate::{
399        Dfa,
400        Nfa,
401        Enfa,
402    };
403
404    #[test]
405    fn test_epsilon() {
406        let expected = Expected::<_, i32> {
407            initial: set![0, 1],
408            transitions: set![],
409            finals: set![set![0, 1]]
410        };
411        let mut actual = Dfa::new(set![0, 1]);
412        let s0 = actual.initial_index();
413        actual.set_final(s0);
414        assert_eq(expected, actual);
415    }
416
417    #[test]
418    fn test_symbol() {
419        let expected = Expected {
420            initial: set![0],
421            transitions: set![
422                (set![0], Segment::singleton(A), set![1])
423            ],
424            finals: set![set![1]]
425        };
426        let mut actual = Dfa::new(set![0]);
427        let s0 = actual.initial_index();
428        let s1 = actual.states_insert(set![1]);
429        actual.transitions_insert((s0, Segment::singleton(A), s1));
430        actual.set_final(s1);
431        assert_eq(expected, actual);
432    }
433
434    #[test]
435    fn test_alternation() {
436        let expected = Expected {
437            initial: set![0, 1, 2, 3, 4],
438            transitions: set![
439                (set![0, 1, 2, 3, 4], Segment::singleton(A), set![1, 5])
440            ],
441            finals: set![set![0, 1, 2, 3, 4], set![1, 5]]
442        };
443        let mut actual = Dfa::new(set![0, 1, 2, 3, 4]);
444        let s01234 = actual.initial_index();
445        let s15 = actual.states_insert(set![1, 5]);
446        actual.transitions_insert((s01234, Segment::singleton(A), s15));
447        actual.set_final(s01234);
448        actual.set_final(s15);
449        assert_eq(expected, actual);
450    }
451
452    #[test]
453    fn test_concatenation() {
454        let expected = Expected {
455            initial: set![0, 2],
456            transitions: set![
457                (set![0, 2], Segment::singleton(A), set![1, 3, 4, 5])
458            ],
459            finals: set![set![1, 3, 4, 5]]
460        };
461        let mut actual = Dfa::new(set![0, 2]);
462        let s02 = actual.initial_index();
463        let s1345 = actual.states_insert(set![1, 3, 4, 5]);
464        actual.transitions_insert((s02, Segment::singleton(A), s1345));
465        actual.set_final(s1345);
466        assert_eq(expected, actual);
467    }
468
469    #[test]
470    fn test_repetition() {
471        let expected = Expected {
472            initial: set![0, 1, 2],
473            transitions: set![
474                (set![0, 1, 2], Segment::singleton(A), set![1, 2, 3]),
475                (set![1, 2, 3], Segment::singleton(A), set![1, 2, 3])
476            ],
477            finals: set![set![0, 1, 2], set![1, 2, 3]]
478        };
479        let mut actual = Dfa::new(set![0, 1, 2]);
480        let s012 = actual.initial_index();
481        let s123 = actual.states_insert(set![1, 2, 3]);
482        actual.transitions_insert((s012, Segment::singleton(A), s123));
483        actual.transitions_insert((s123, Segment::singleton(A), s123));
484        actual.set_final(s012);
485        actual.set_final(s123);
486        assert_eq(expected, actual);
487    }
488
489    #[test]
490    fn test_nondeterminism() {
491        let mut actual = Dfa::new(set![0]);
492        let s0 = actual.initial_index();
493        let s1 = actual.states_insert(set![1]);
494        let s2 = actual.states_insert(set![2]);
495        actual.transitions_insert((s0, Segment::singleton(A), s1));
496        assert!(std::panic::catch_unwind(move || actual.transitions_insert((s0, Segment::singleton(A), s2))).is_err());
497    }
498
499    #[test]
500    fn test_nondeterminism_segments() {
501        let mut actual = Dfa::new(set![0]);
502        let s0 = actual.initial_index();
503        let s1 = actual.states_insert(set![1]);
504        let s2 = actual.states_insert(set![2]);
505        actual.transitions_insert((s0, Segment::closed_open(A, C), s1));
506        assert!(std::panic::catch_unwind(move || actual.transitions_insert((s0, Segment::closed_open(B, D), s2))).is_err());
507    }
508
509    #[test]
510    fn test_from_enfa_epsilon() {
511        let expected = Expected::<_, i32> {
512            initial: set![0, 1],
513            transitions: set![],
514            finals: set![set![0, 1]]
515        };
516        let mut enfa = Enfa::new(0);
517        let s0 = enfa.initial_index();
518        let s1 = enfa.states_insert(1);
519        enfa.transitions_insert((s0, Segment::empty(), s1));
520        enfa.set_final(s1);
521        let actual = Dfa::from(&enfa);
522        assert_eq(expected, actual);
523    }
524
525    #[test]
526    fn test_from_enfa_symbol() {
527        let expected = Expected {
528            initial: set![0],
529            transitions: set![
530                (set![0], Segment::singleton(A), set![1])
531            ],
532            finals: set![set![1]]
533        };
534        let mut enfa = Enfa::new(0);
535        let s0 = enfa.initial_index();
536        let s1 = enfa.states_insert(1);
537        enfa.transitions_insert((s0, Segment::singleton(A), s1));
538        enfa.set_final(s1);
539        let actual = Dfa::from(&enfa);
540        assert_eq(expected, actual);
541    }
542
543    #[test]
544    fn test_from_enfa_alternation() {
545        let expected = Expected {
546            initial: set![0, 1, 2, 3, 4],
547            transitions: set![
548                (set![0, 1, 2, 3, 4], Segment::singleton(A), set![1, 5])
549            ],
550            finals: set![set![0, 1, 2, 3, 4], set![1, 5]]
551        };
552        let mut enfa = Enfa::new(0);
553        let s0 = enfa.initial_index();
554        let s1 = enfa.states_insert(1);
555        let s2 = enfa.states_insert(2);
556        let s3 = enfa.states_insert(3);
557        let s4 = enfa.states_insert(4);
558        let s5 = enfa.states_insert(5);
559        enfa.transitions_insert((s0, Segment::empty(), s2));
560        enfa.transitions_insert((s0, Segment::empty(), s4));
561        enfa.transitions_insert((s2, Segment::empty(), s3));
562        enfa.transitions_insert((s4, Segment::singleton(A), s5));
563        enfa.transitions_insert((s3, Segment::empty(), s1));
564        enfa.transitions_insert((s5, Segment::empty(), s1));
565        enfa.set_final(s1);
566        let actual = Dfa::from(&enfa);
567        assert_eq(expected, actual);
568    }
569
570    #[test]
571    fn test_from_enfa_concatenation() {
572        let expected = Expected {
573            initial: set![0, 2],
574            transitions: set![
575                (set![0, 2], Segment::singleton(A), set![1, 3, 4, 5])
576            ],
577            finals: set![set![1, 3, 4, 5]]
578        };
579        let mut enfa = Enfa::new(0);
580        let s0 = enfa.initial_index();
581        let s1 = enfa.states_insert(1);
582        let s2 = enfa.states_insert(2);
583        let s3 = enfa.states_insert(3);
584        let s4 = enfa.states_insert(4);
585        let s5 = enfa.states_insert(5);
586        enfa.transitions_insert((s0, Segment::empty(), s2));
587        enfa.transitions_insert((s2, Segment::singleton(A), s3));
588        enfa.transitions_insert((s3, Segment::empty(), s4));
589        enfa.transitions_insert((s4, Segment::empty(), s5));
590        enfa.transitions_insert((s5, Segment::empty(), s1));
591        enfa.set_final(s1);
592        let actual = Dfa::from(&enfa);
593        assert_eq(expected, actual);
594    }
595
596    #[test]
597    fn test_from_enfa_repetition() {
598        let expected = Expected {
599            initial: set![0, 1, 2],
600            transitions: set![
601                (set![0, 1, 2], Segment::singleton(A), set![1, 2, 3]),
602                (set![1, 2, 3], Segment::singleton(A), set![1, 2, 3])
603            ],
604            finals: set![set![0, 1, 2], set![1, 2, 3]]
605        };
606        let mut enfa = Enfa::new(0);
607        let s0 = enfa.initial_index();
608        let s1 = enfa.states_insert(1);
609        let s2 = enfa.states_insert(2);
610        let s3 = enfa.states_insert(3);
611        enfa.transitions_insert((s0, Segment::empty(), s1));
612        enfa.transitions_insert((s0, Segment::empty(), s2));
613        enfa.transitions_insert((s2, Segment::singleton(A), s3));
614        enfa.transitions_insert((s3, Segment::empty(), s2));
615        enfa.transitions_insert((s3, Segment::empty(), s1));
616        enfa.set_final(s1);
617        let actual = Dfa::from(&enfa);
618        assert_eq(expected, actual);
619    }
620
621    #[test]
622    fn test_from_enfa_nondeterminism() {
623        let expected = Expected {
624            initial: set![0, 1, 3, 4],
625            transitions: set![
626                (set![0, 1, 3, 4], Segment::singleton(A), set![2, 3, 4])
627            ],
628            finals: set![set![0, 1, 3, 4], set![2, 3, 4]]
629        };
630        let mut enfa = Enfa::new(0);
631        let s0 = enfa.initial_index();
632        let s1 = enfa.states_insert(1);
633        let s2 = enfa.states_insert(2);
634        let s3 = enfa.states_insert(3);
635        let s4 = enfa.states_insert(4);
636        enfa.transitions_insert((s0, Segment::empty(), s1));
637        enfa.transitions_insert((s1, Segment::singleton(A), s2));
638        enfa.transitions_insert((s1, Segment::singleton(A), s3));
639        enfa.transitions_insert((s0, Segment::empty(), s3));
640        enfa.transitions_insert((s2, Segment::empty(), s4));
641        enfa.transitions_insert((s3, Segment::empty(), s4));
642        enfa.set_final(s4);
643        let actual = Dfa::from(&enfa);
644        assert_eq(expected, actual);
645    }
646
647    #[test]
648    fn test_from_nfa_epsilon() {
649        let expected = Expected::<_, i32> {
650            initial: set![0],
651            transitions: set![],
652            finals: set![set![0]]
653        };
654        let mut nfa: Nfa<_, i32> = Nfa::new(0);
655        let s0 = nfa.initial_index();
656        nfa.set_final(s0);
657        let actual = Dfa::from(&nfa);
658        assert_eq(expected, actual);
659    }
660
661    #[test]
662    fn test_from_nfa_symbol() {
663        let expected = Expected {
664            initial: set![0],
665            transitions: set![
666                (set![0], Segment::singleton(A), set![1])
667            ],
668            finals: set![set![1]]
669        };
670        let mut nfa = Nfa::new(0);
671        let s0 = nfa.initial_index();
672        let s1 = nfa.states_insert(1);
673        nfa.transitions_insert((s0, Segment::singleton(A), s1));
674        nfa.set_final(s1);
675        let actual = Dfa::from(&nfa);
676        assert_eq(expected, actual);
677    }
678
679    #[test]
680    fn test_from_nfa_alternation() {
681        let expected = Expected {
682            initial: set![0],
683            transitions: set![
684                (set![0], Segment::singleton(A), set![1])
685            ],
686            finals: set![set![0], set![1]]
687        };
688        let mut nfa = Nfa::new(0);
689        let s0 = nfa.initial_index();
690        let s1 = nfa.states_insert(1);
691        nfa.transitions_insert((s0, Segment::singleton(A), s1));
692        nfa.set_final(s0);
693        nfa.set_final(s1);
694        let actual = Dfa::from(&nfa);
695        assert_eq(expected, actual);
696    }
697
698    #[test]
699    fn test_from_nfa_concatenation() {
700        let expected = Expected {
701            initial: set![0],
702            transitions: set![
703                (set![0], Segment::singleton(A), set![1])
704            ],
705            finals: set![set![1]]
706        };
707        let mut nfa = Nfa::new(0);
708        let s0 = nfa.initial_index();
709        let s1 = nfa.states_insert(1);
710        nfa.transitions_insert((s0, Segment::singleton(A), s1));
711        nfa.set_final(s1);
712        let actual = Dfa::from(&nfa);
713        assert_eq(expected, actual);
714    }
715
716    #[test]
717    fn test_from_nfa_repetition() {
718        let expected = Expected {
719            initial: set![0],
720            transitions: set![
721                (set![0], Segment::singleton(A), set![1]),
722                (set![1], Segment::singleton(A), set![1])
723            ],
724            finals: set![set![0], set![1]]
725        };
726        let mut nfa = Nfa::new(0);
727        let s0 = nfa.initial_index();
728        let s1= nfa.states_insert(1);
729        nfa.transitions_insert((s0, Segment::singleton(A), s1));
730        nfa.transitions_insert((s1, Segment::singleton(A), s1));
731        nfa.set_final(s0);
732        nfa.set_final(s1);
733        let actual = Dfa::from(&nfa);
734        assert_eq(expected, actual);
735    }
736
737    #[test]
738    fn test_from_nfa_nondeterministic() {
739        let expected = Expected {
740            initial: set![0],
741            transitions: set![
742                (set![0], Segment::singleton(A), set![1, 2]),
743                (set![0], Segment::singleton(B), set![1])
744            ],
745            finals: set![set![1], set![1, 2]]
746        };
747        let mut nfa = Nfa::new(0);
748        let s0 = nfa.initial_index();
749        let s1 = nfa.states_insert(1);
750        let s2 = nfa.states_insert(2);
751        nfa.transitions_insert((s0, Segment::singleton(A), s1));
752        nfa.transitions_insert((s0, Segment::singleton(A), s2));
753        nfa.transitions_insert((s0, Segment::singleton(B), s1));
754        nfa.set_final(s1);
755        nfa.set_final(s2);
756        let actual = Dfa::from(&nfa);
757        assert_eq(expected, actual);
758    }
759
760    struct Expected<S, T> {
761        initial: S,
762        transitions: Set<(S, Segment<T>, S)>,
763        finals: Set<S>,
764    }
765
766    fn assert_eq<S: Clone + Debug + Ord, T: Clone + Debug + Ord>(expected: Expected<S, T>, actual: Dfa<S, T>) {
767        assert_eq!(expected.initial, actual.states_index(actual.initial_index()).clone());
768        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());
769        assert_eq!(expected.finals, actual.states_slice(actual.final_indices()).cloned().collect());
770    }
771
772    static A: i32 = 0;
773    static B: i32 = 2;
774    static C: i32 = 4;
775    static D: i32 = 6;
776}
finite_automata/dfa.rs

finite_automata/
dfa.rs
