Obtain the transition table from a dense DFA

[borchero]

As the title says ... is there any way to obtain the internal transition table from a dense DFA? I'd like to use the DFA to compute the min and max length of a string matching the regex. With access to the transition table, my initial assumption would be that this is pretty straightforward when interpreting the transition table as the adjacency matrix of a graph:

• Min length is given as the shortest path through the graph
• Max length is given as the number of nodes in the graph unless there's a loop in the graph (in which case the max is undefined/infinite)

Thanks for any help 🙏🏼

[BurntSushi]

Yup! You can use the Automaton trait. You should only need Automaton::start_state, Automaton::next_state and Automaton::next_eoi_state.

[borchero]

Thanks for your super quick reply @BurntSushi! 😄 I just had a look at trait and the functions you mentioned but I'm not entirely sure that serves the purpose I had in mind 🧐 next_state requires me to know a valid character to perform a graph transition -- however, for each state, I essentially need to know "what valid transitions are there?" in order to extract "meta-information" from the graph. After all, the min- and max length of a string valid under a certain regex is independent of the any "input characters" (which I seem to need for using next_state).

[BurntSushi]

You do a graph traversal by looking at all states for the alphabet. The alphabet is every valid u8 (and the special EOI transition, which you need to use next_eoi_state for). The special dead state can never lead to a match.

There's nothing being hidden here that you can't get at with next_state as far as I can tell. If you had the internal representation, it would just be a &[StateID]. That's it. And if you want an iterator of "valid" states, that would be slice.iter().filter(|state_id| !dfa.is_dead_state(state_id)).

[borchero]

Ah nice, thanks for your help @BurntSushi, I managed to figure it out 😄 instead of iterating over all u8s, I'm using dfa.byte_classes().representatives(0..=255) now though, that seemed like the more efficient option (and not knowing about this was probably the main source of my earlier confusion) ... that allows running a reasonably efficient BFS via next_state! :)

[BurntSushi]

Yes, byte classes is a nice optimization. But it's strictly an optimization. Using every u8 value is also precisely correct.