Creating a DFA for regex with backreferences if the strings are of finite and known length

[asasine]

Hello! I understand that under most circumstances, a regex using backreferences cannot be recognized by a DFA since the language isn't regular. However, does this change if the strings recognized by that language are of a predetermined length?

My question is inspired by regex crosswords and a brief section on a blog post about solving them. The MIT crossword regex .*(.)(.)(.)(.)\4\3\2\1.* would normally be non-regular due to the backreferences but given the string is known to be of length 12, the regex can be expanded to ....AAAAAAAA|...AAAAAAAA.|..AAAAAAAA..|.AAAAAAAA...|AAAAAAAA....|....AAABBAAA|...AAABBAAA.|etc.). There are a lot of possibilities here (4 * 26^4 or 1,827,904 by my math) but a finite number, so could a DFA be constructed?

Given this hypothetical DFA, possibly even a regex_automata::dfa::dense::DFA, I then wanted to apply the ideas within another blog post, which performs DFA intersections, to create a linear DFA that recognizes the entire crossword. However, I don't see any APIs for DFA that allow retrieving the states directly, only APIs for walking the DFA given character inputs. Do they exist?

Another idea would be to take the DFA, perform a topological sort to find the set of possible characters at a given position in the input string, and perform constraint solving and searching/backtracking to solve the regex crossword. This would also require access to the DFA's states. Is this possible?

Sorry for what amounted to a bit of a ramble. The regex crate and friends is excellent and I wanted to evaluate it before I dove into building a custom DFA solution.

[BurntSushi]

so could a DFA be constructed?

If you can translate the regex with backreferences to an actual regular expressing, then, yes, of course, you could generate a DFA.

But if you're talking about a regex with over a million different branches, then good luck. It probably won't go over well. And note that this crate has a limit on the total number of states in a DFA that it can generate (based on how many states can be represented in ~32 bits). That limit might seem constraining, but in practice, a DFA that big is going to take a very very long time to generate and generally be completely unwieldy to actually use.

However, I don't see any APIs for DFA that allow retrieving the states directly, only APIs for walking the DFA given character inputs. Do they exist?

Well, what would the API you want actually look like? I claim that it would basically amount to what's on the Automaton trait. The Automaton trait lets you "walk the DFA." (It's unclear to me if you've found the Automaton trait since you don't mention it explicitly, but I'm guessing you did.) It exposes state IDs. You can get the starting state IDs. And for a state ID, you can ask what its transitions are for each element in the alphabet.

[asasine]

Considering the alphabet I'm dealing with is considerablly smaller than a u8, I think a custom DFA construction is sufficient and alleviates some of the unwieldiness. The gendfa example you provided was helpful to understand how to walk the DFA through the Automaton trait, specifically StateTransitionIter.

[BurntSushi]

I wanted to evaluate it before I dove into building a custom DFA solution.

If you're just doing this "for fun," then one very quick way to do this would be to just fork regex-automata and modify its DFA construction algorithm. Or, at the very least, make use of regex-automata's Thompson NFA construction. There is a lot of work that goes into NFA construction. Simple DFA construction is a bit simpler (albeit with many optimization tricks).

[BurntSushi]

Incidentally, I just wrote a code generator that converts a DFA to Rust code here: https://github.com/BurntSushi/duration-unit-lookup/blob/master/gendfa/main.rs

It uses regex-automata. It demonstrates how to traverse the graph of a DFA.

It is not a "full" example in the sense that the code generator is correct for all possible DFAs. But it should be a good starting point depending on what you're doing.

[asasine]

Reading through this was quite helpful and gave me some ideas on how I could perform the topological sort I mentioned above. Thanks!