finite_automata/
nfa.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    Dfa,
19    StatesContains,
20    StatesIndex,
21    StatesSlice,
22    states_contains_from,
23    states_contains_closure_from,
24};
25
26/// A nondeterministic finite automaton.
27#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
28pub struct Nfa<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, Map<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> Nfa<S, T> {
40    /// Create a new nondeterministic finite automaton with the given initial state.
41    pub fn new(initial: S) -> Nfa<S, T> {
42        Nfa {
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> Nfa<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> Nfa<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, |targets| {
104                if let Some(mut targets) = targets {
105                    if targets.get(&target_index).is_some() {
106                        panic!("transition segments must not overlap");
107                    }
108                    targets.insert(target_index, transition_index);
109                    Some(targets)
110                } else {
111                    Some(map![target_index => transition_index])
112                }
113            });
114        } else {
115            self.transition_to_index.insert(source_index, segment_map![transition_segment.clone() => map![target_index => transition_index]]);
116        }
117        self.index_to_transition.insert(transition_index, (source_index, transition_segment, target_index));
118        transition_index
119    }
120}
121
122impl<S: Ord, T: Ord> Nfa<S, T> {
123    /// Return the transition index of the transition, if it exists.
124    pub fn transitions_contains(&self, transition: (StateIndex, &T, StateIndex)) -> Option<TransitionIndex> {
125        let (source_index, transition_element, target_index) = transition;
126        self.transition_to_index.get(&source_index).and_then(|transitions| transitions.get(transition_element).and_then(|targets| targets.get(&target_index)).copied())
127    }
128
129    /// Get the transition at the transition index.
130    pub fn transitions_index(&self, transition_index: TransitionIndex) -> (StateIndex, &Segment<T>, StateIndex) {
131        let (source_index, transition, target_index) = self.index_to_transition.get(&transition_index).expect("transition index out of bounds");
132        (*source_index, transition, *target_index)
133    }
134
135    /// Convert the transition indices to transitions.
136    pub fn transitions_slice<'a>(&'a self, transition_indices: impl IntoIterator<Item = TransitionIndex> + 'a) -> Box<dyn Iterator<Item = (StateIndex, &Segment<T>, StateIndex)> + 'a> {
137        Box::new(transition_indices.into_iter().map(move |transition_index| self.transitions_index(transition_index)))
138    }
139
140    /// Get all the transition indices.
141    pub fn transition_indices<'a>(&'a self) -> Box<dyn Iterator<Item = TransitionIndex> + 'a> {
142        Box::new(self.index_to_transition.keys().copied())
143    }
144
145    /// Get the transition indices originating at the state index.
146    pub fn transition_indices_from<'a>(&'a self, state_index: StateIndex) -> Box<dyn Iterator<Item = TransitionIndex> + 'a> {
147        if self.index_to_state.get(&state_index).is_none() {
148            panic!("state index out of bounds");
149        }
150        if let Some(transitions_from) = self.transition_to_index.get(&state_index) {
151            Box::new(transitions_from.iter().flat_map(|(_, targets_from)| targets_from.iter().map(|(_, transition_index_from)| transition_index_from)).copied())
152        } else {
153            Box::new(iter::empty())
154        }
155    }
156
157    /// Get the index of the initial state.
158    pub fn initial_index(&self) -> StateIndex {
159        self.initial_index
160    }
161
162    /// Check if the state at the state index is a final state.
163    pub fn is_final(&self, state_index: StateIndex) -> bool {
164        self.final_indices.contains(&state_index)
165    }
166    
167    /// Set the state at the state index as a final state.
168    pub fn set_final(&mut self, state_index: StateIndex) {
169        self.final_indices.insert(state_index);
170    }
171
172    /// Get all the state indices for final states.
173    pub fn final_indices<'a>(&'a self) -> Box<dyn Iterator<Item = StateIndex> + 'a> {
174        Box::new(self.final_indices.iter().copied())
175    }
176}
177
178impl<S: Clone + Ord, T: Clone + Ord> From<&Enfa<S, T>> for Nfa<Set<S>, T> {
179    /// Create a new nondeterministic finite automaton from the nondeterministic finite automaton with epsilon moves.
180    fn from(enfa: &Enfa<S, T>) -> Nfa<Set<S>, T> {
181        let initial_closure_indices: Set<StateIndex> = enfa.closure_indices(enfa.initial_index()).collect();
182        let initial_closure = enfa.states_slice(initial_closure_indices.iter().copied()).cloned().collect();
183        let mut stack = vec![initial_closure_indices];
184        let mut nfa = Nfa::new(initial_closure);
185        while let Some(source_closure_indices) = stack.pop() {
186            let source_index = states_contains_closure_from(&nfa, enfa, source_closure_indices.iter().copied()).expect("closure does not exist");
187            for &source_closure_index in &source_closure_indices {
188                if enfa.is_final(source_closure_index) {
189                    nfa.set_final(source_index);
190                }
191                for transition_index in enfa.transition_indices_from(source_closure_index) {
192                    let (_, transition, target_index) = enfa.transitions_index(transition_index);
193                    if !transition.is_empty() {
194                        let target_closure_indices: Set<StateIndex> = enfa.closure_indices(target_index).collect();
195                        if let Some(target_index) = states_contains_closure_from(&nfa, enfa, target_closure_indices.iter().copied()) {
196                            nfa.transitions_insert((source_index, transition.clone(), target_index));
197                        } else {
198                            let target_closure = enfa.states_slice(target_closure_indices.iter().copied()).cloned().collect();
199                            stack.push(target_closure_indices);
200                            let target_index = nfa.states_insert(target_closure);
201                            nfa.transitions_insert((source_index, transition.clone(), target_index));
202                        }
203                    }
204                }
205            }
206        }
207        nfa
208    }
209}
210
211impl<S: Clone + Ord, T: Clone + Ord> From<&Dfa<S, T>> for Nfa<S, T> {
212    /// Create a new nondeterministic finite automaton from the deterministic finite automaton.
213    fn from(dfa: &Dfa<S, T>) -> Nfa<S, T> {
214        let initial = dfa.states_index(dfa.initial_index());
215        let mut nfa = Nfa::new(initial.clone());
216        for state_index in dfa.state_indices() {
217            let state = dfa.states_index(state_index);
218            nfa.states_insert(state.clone());
219        }
220        for transition_index in dfa.transition_indices() {
221            let (source_index, transition, target_index) = dfa.transitions_index(transition_index);
222            let source_index = states_contains_from(&nfa, dfa, source_index).expect("state does not exist");
223            let target_index = states_contains_from(&nfa, dfa, target_index).expect("state does not exist");
224            nfa.transitions_insert((source_index, transition.clone(), target_index));
225        }
226        for final_index in dfa.final_indices() {
227            let final_index = states_contains_from(&nfa, dfa, final_index).expect("state does not exist");
228            nfa.set_final(final_index);
229        }
230        nfa
231    }
232}
233
234impl<S: Clone + Ord, T: Clone + Ord> Subsume<Enfa<S, T>> for Nfa<Set<S>, T> {
235    /// Insert all the states and transitions of the nondeterministic finite automaton with epsilon moves.
236    fn subsume(&mut self, enfa: &Enfa<S, T>) {
237        let initial_closure_indices: Set<StateIndex> = enfa.closure_indices(enfa.initial_index()).collect();
238        let initial_closure = enfa.states_slice(initial_closure_indices.iter().copied()).cloned().collect();
239        let mut stack = vec![initial_closure_indices];
240        self.states_insert(initial_closure);
241        while let Some(source_closure_indices) = stack.pop() {
242            let source_index = states_contains_closure_from(self, enfa, source_closure_indices.iter().copied()).expect("closure does not exist");
243            for &source_closure_index in &source_closure_indices {
244                if enfa.is_final(source_closure_index) {
245                    self.set_final(source_index);
246                }
247                for transition_index in enfa.transition_indices_from(source_closure_index) {
248                    let (_, transition, target_index) = enfa.transitions_index(transition_index);
249                    if !transition.is_empty() {
250                        let target_closure_indices: Set<StateIndex> = enfa.closure_indices(target_index).collect();
251                        if let Some(target_index) = states_contains_closure_from(self, enfa, target_closure_indices.iter().copied()) {
252                            self.transitions_insert((source_index, transition.clone(), target_index));
253                        } else {
254                            let target_closure = enfa.states_slice(target_closure_indices.iter().copied()).cloned().collect();
255                            stack.push(target_closure_indices);
256                            let target_index = self.states_insert(target_closure);
257                            self.transitions_insert((source_index, transition.clone(), target_index));
258                        }
259                    }
260                }
261            }
262        }
263    }
264}
265
266impl<S: Clone + Ord, T: Clone + Ord> Subsume<Nfa<S, T>> for Nfa<S, T> {
267    /// Insert all the states and transitions of the nondeterministic finite automaton.
268    fn subsume(&mut self, nfa: &Nfa<S, T>) {
269        for state_index in nfa.state_indices() {
270            let state = nfa.states_index(state_index);
271            self.states_insert(state.clone());
272        }
273        for transition_index in nfa.transition_indices() {
274            let (source_index, transition, target_index) = nfa.transitions_index(transition_index);
275            let source_index = states_contains_from(self, nfa, source_index).expect("state does not exist");
276            let target_index = states_contains_from(self, nfa, target_index).expect("state does not exist");
277            self.transitions_insert((source_index, transition.clone(), target_index));
278        }
279    }
280}
281
282impl<S: Clone + Ord, T: Clone + Ord> Subsume<Dfa<S, T>> for Nfa<S, T> {
283    /// Insert all the states and transitions of the deterministic finite automaton.
284    fn subsume(&mut self, dfa: &Dfa<S, T>) {
285        for state_index in dfa.state_indices() {
286            let state = dfa.states_index(state_index);
287            self.states_insert(state.clone());
288        }
289        for transition_index in dfa.transition_indices() {
290            let (source_index, transition, target_index) = dfa.transitions_index(transition_index);
291            let source_index = states_contains_from(self, dfa, source_index).expect("state does not exist");
292            let target_index = states_contains_from(self, dfa, target_index).expect("state does not exist");
293            self.transitions_insert((source_index, transition.clone(), target_index));
294        }
295    }
296}
297
298impl<S: Ord, T: Ord> StatesContains<S> for Nfa<S, T> {
299    fn states_contains(&self, state: &S) -> Option<StateIndex> {
300        self.states_contains(state)
301    }
302}
303
304impl<S: Ord, T: Ord> StatesIndex<S> for Nfa<S, T> {
305    fn states_index(&self, state_index: StateIndex) -> &S {
306        self.states_index(state_index)
307    }
308}
309
310impl<S: Ord, T: Ord> StatesSlice<S> for Nfa<S, T> {
311    fn states_slice<'a>(&'a self, state_indices: impl IntoIterator<Item = StateIndex> + 'a) -> Box<dyn Iterator<Item = &S> + 'a> {
312        self.states_slice(state_indices)
313    }
314}
315
316#[cfg(test)]
317mod tests {
318    use std::{
319        collections::BTreeSet as Set,
320        fmt::Debug,
321    };
322    use segment_map::Segment;
323    use crate::{
324        Nfa,
325        Enfa,
326    };
327
328    #[test]
329    fn test_epsilon() {
330        let expected = Expected::<_, i32> {
331            initial: set![0, 1],
332            transitions: set![],
333            finals: set![set![0, 1]]
334        };
335        let mut actual = Nfa::new(set![0, 1]);
336        let s0 = actual.initial_index();
337        actual.set_final(s0);
338        assert_eq(expected, actual);
339    }
340
341    #[test]
342    fn test_symbol() {
343        let expected = Expected {
344            initial: set![0],
345            transitions: set![
346                (set![0], Segment::singleton(A), set![1])
347            ],
348            finals: set![set![1]]
349        };
350        let mut actual = Nfa::new(set![0]);
351        let s0 = actual.initial_index();
352        let s1 = actual.states_insert(set![1]);
353        actual.transitions_insert((s0, Segment::singleton(A), s1));
354        actual.set_final(s1);
355        assert_eq(expected, actual);
356    }
357
358    #[test]
359    fn test_alternation() {
360        let expected = Expected {
361            initial: set![0, 1, 2, 3, 4],
362            transitions: set![
363                (set![0, 1, 2, 3, 4], Segment::singleton(A), set![1, 5])
364            ],
365            finals: set![set![0, 1, 2, 3, 4], set![1, 5]]
366        };
367        let mut actual = Nfa::new(set![0, 1, 2, 3, 4]);
368        let s01234 = actual.initial_index();
369        let s15 = actual.states_insert(set![1, 5]);
370        actual.transitions_insert((s01234, Segment::singleton(A), s15));
371        actual.set_final(s01234);
372        actual.set_final(s15);
373        assert_eq(expected, actual);
374    }
375
376    #[test]
377    fn test_concatenation() {
378        let expected = Expected {
379            initial: set![0, 2],
380            transitions: set![
381                (set![0, 2], Segment::singleton(A), set![1, 3, 4, 5])
382            ],
383            finals: set![set![1, 3, 4, 5]]
384        };
385        let mut actual = Nfa::new(set![0, 2]);
386        let s02 = actual.initial_index();
387        let s1345 = actual.states_insert(set![1, 3, 4, 5]);
388        actual.transitions_insert((s02, Segment::singleton(A), s1345));
389        actual.set_final(s1345);
390        assert_eq(expected, actual);
391    }
392
393    #[test]
394    fn test_repetition() {
395        let expected = Expected {
396            initial: set![0, 1, 2],
397            transitions: set![
398                (set![0, 1, 2], Segment::singleton(A), set![1, 2, 3]),
399                (set![1, 2, 3], Segment::singleton(A), set![1, 2, 3])
400            ],
401            finals: set![set![0, 1, 2], set![1, 2, 3]]
402        };
403        let mut actual = Nfa::new(set![0, 1, 2]);
404        let s012 = actual.initial_index();
405        let s123 = actual.states_insert(set![1, 2, 3]);
406        actual.transitions_insert((s012, Segment::singleton(A), s123));
407        actual.transitions_insert((s123, Segment::singleton(A), s123));
408        actual.set_final(s012);
409        actual.set_final(s123);
410        assert_eq(expected, actual);
411    }
412
413    #[test]
414    fn test_nondeterminism() {
415        let expected = Expected {
416            initial: set![0, 2, 4],
417            transitions: set![
418                (set![0, 2, 4], Segment::singleton(A), set![1, 3]),
419                (set![0, 2, 4], Segment::singleton(A), set![1, 5])
420            ],
421            finals: set![set![1, 3], set![1, 5]]
422        };
423        let mut actual = Nfa::new(set![0, 2, 4]);
424        let s024 = actual.initial_index();
425        let s13 = actual.states_insert(set![1, 3]);
426        let s15 = actual.states_insert(set![1, 5]);
427        actual.transitions_insert((s024, Segment::singleton(A), s13));
428        actual.transitions_insert((s024, Segment::singleton(A), s15));
429        actual.set_final(s13);
430        actual.set_final(s15);
431        assert_eq(expected, actual);
432    }
433
434    #[test]
435    fn test_nondeterminism_segments() {
436        let expected = Expected {
437            initial: set![0],
438            transitions: set![
439                (set![0], Segment::closed_open(A, C), set![1]),
440                (set![0], Segment::closed_open(B, D), set![2])
441            ],
442            finals: set![set![1], set![2]]
443        };
444        let mut actual = Nfa::new(set![0]);
445        let s0 = actual.initial_index();
446        let s1 = actual.states_insert(set![1]);
447        let s2 = actual.states_insert(set![2]);
448        let t0 = actual.transitions_insert((s0, Segment::closed_open(A, C), s1));
449        let t1 = actual.transitions_insert((s0, Segment::closed_open(B, D), s2));
450        actual.set_final(s1);
451        actual.set_final(s2);
452        assert_eq!(Some(t0), actual.transitions_contains((s0, &A, s1)));
453        assert_eq!(Some(t0), actual.transitions_contains((s0, &B, s1)));
454        assert_eq!(None, actual.transitions_contains((s0, &C, s1)));
455        assert_eq!(None, actual.transitions_contains((s0, &D, s1)));
456        assert_eq!(None, actual.transitions_contains((s0, &A, s2)));
457        assert_eq!(Some(t1), actual.transitions_contains((s0, &B, s2)));
458        assert_eq!(Some(t1), actual.transitions_contains((s0, &C, s2)));
459        assert_eq!(None, actual.transitions_contains((s0, &D, s2)));
460        assert_eq(expected, actual);
461    }
462
463    #[test]
464    fn test_from_enfa_epsilon() {
465        let expected = Expected::<_, i32> {
466            initial: set![0, 1],
467            transitions: set![],
468            finals: set![set![0, 1]]
469        };
470        let mut enfa = Enfa::new(0);
471        let s0 = enfa.initial_index();
472        let s1 = enfa.states_insert(1);
473        enfa.transitions_insert((s0, Segment::empty(), s1));
474        enfa.set_final(s1);
475        let actual = Nfa::from(&enfa);
476        assert_eq(expected, actual);
477    }
478
479    #[test]
480    fn test_from_enfa_symbol() {
481        let expected = Expected {
482            initial: set![0],
483            transitions: set![
484                (set![0], Segment::singleton(A), set![1])
485            ],
486            finals: set![set![1]]
487        };
488        let mut enfa = Enfa::new(0);
489        let s0 = enfa.initial_index();
490        let s1 = enfa.states_insert(1);
491        enfa.transitions_insert((s0, Segment::singleton(A), s1));
492        enfa.set_final(s1);
493        let actual = Nfa::from(&enfa);
494        assert_eq(expected, actual);
495    }
496
497    #[test]
498    fn test_from_enfa_alternation() {
499        let expected = Expected {
500            initial: set![0, 1, 2, 3, 4],
501            transitions: set![
502                (set![0, 1, 2, 3, 4], Segment::singleton(A), set![1, 5])
503            ],
504            finals: set![set![0, 1, 2, 3, 4], set![1, 5]]
505        };
506        let mut enfa = Enfa::new(0);
507        let s0 = enfa.initial_index();
508        let s1 = enfa.states_insert(1);
509        let s2 = enfa.states_insert(2);
510        let s3 = enfa.states_insert(3);
511        let s4 = enfa.states_insert(4);
512        let s5 = enfa.states_insert(5);
513        enfa.transitions_insert((s0, Segment::empty(), s2));
514        enfa.transitions_insert((s0, Segment::empty(), s4));
515        enfa.transitions_insert((s2, Segment::empty(), s3));
516        enfa.transitions_insert((s4, Segment::singleton(A), s5));
517        enfa.transitions_insert((s3, Segment::empty(), s1));
518        enfa.transitions_insert((s5, Segment::empty(), s1));
519        enfa.set_final(s1);
520        let actual = Nfa::from(&enfa);
521        assert_eq(expected, actual);
522    }
523
524    #[test]
525    fn test_from_enfa_concatenation() {
526        let expected = Expected {
527            initial: set![0, 2],
528            transitions: set![
529                (set![0, 2], Segment::singleton(A), set![1, 3, 4, 5])
530            ],
531            finals: set![set![1, 3, 4, 5]]
532        };
533        let mut enfa = Enfa::new(0);
534        let s0 = enfa.initial_index();
535        let s1 = enfa.states_insert(1);
536        let s2 = enfa.states_insert(2);
537        let s3 = enfa.states_insert(3);
538        let s4 = enfa.states_insert(4);
539        let s5 = enfa.states_insert(5);
540        enfa.transitions_insert((s0, Segment::empty(), s2));
541        enfa.transitions_insert((s2, Segment::singleton(A), s3));
542        enfa.transitions_insert((s3, Segment::empty(), s4));
543        enfa.transitions_insert((s4, Segment::empty(), s5));
544        enfa.transitions_insert((s5, Segment::empty(), s1));
545        enfa.set_final(s1);
546        let actual = Nfa::from(&enfa);
547        assert_eq(expected, actual);
548    }
549
550    #[test]
551    fn test_from_enfa_repetition() {
552        let expected = Expected {
553            initial: set![0, 1, 2],
554            transitions: set![
555                (set![0, 1, 2], Segment::singleton(A), set![1, 2, 3]),
556                (set![1, 2, 3], Segment::singleton(A), set![1, 2, 3])
557            ],
558            finals: set![set![0, 1, 2], set![1, 2, 3]]
559        };
560        let mut enfa = Enfa::new(0);
561        let s0 = enfa.initial_index();
562        let s1 = enfa.states_insert(1);
563        let s2 = enfa.states_insert(2);
564        let s3 = enfa.states_insert(3);
565        enfa.transitions_insert((s0, Segment::empty(), s1));
566        enfa.transitions_insert((s0, Segment::empty(), s2));
567        enfa.transitions_insert((s2, Segment::singleton(A), s3));
568        enfa.transitions_insert((s3, Segment::empty(), s2));
569        enfa.transitions_insert((s3, Segment::empty(), s1));
570        enfa.set_final(s1);
571        let actual = Nfa::from(&enfa);
572        assert_eq(expected, actual);
573    }
574
575    struct Expected<S, T> {
576        initial: S,
577        transitions: Set<(S, Segment<T>, S)>,
578        finals: Set<S>,
579    }
580
581    fn assert_eq<S: Clone + Debug + Ord, T: Clone + Debug + Ord>(expected: Expected<S, T>, actual: Nfa<S, T>) {
582        assert_eq!(expected.initial, actual.states_index(actual.initial_index()).clone(), "initial");
583        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");
584        assert_eq!(expected.finals, actual.states_slice(actual.final_indices()).cloned().collect(), "finals");
585    }
586
587    static A: i32 = 0;
588    static B: i32 = 2;
589    static C: i32 = 4;
590    static D: i32 = 6;
591}
finite_automata/nfa.rs

finite_automata/
nfa.rs
