2 ms·
A DFA-based regex engine will spit out an optimal state machine if you give it a regex which just combines all your inputs with the disjunction: 0xC0D3|0xC0
by kazinator 6y ago
A DFA-based regex engine will spit out an optimal state machine if you give it a regex which just combines all your inputs with the disjunction:
0xC0D3|0xC0FD|...|0xBEEF
For example, NFA-DFA subset construction algorithm will implicitly figure out that every branch starts with 0x, and so the initial state will have only a single transition out of it on the character 0, and the next state on the character x.
If we feed it every 16 bit hex string from 0x0000 to 0xFFFF, it should reduce to just 7 states:
S0 -[0]-> S1 -[x]-> S2 -[01234569789ABCDEF]-> S3 ...
What you need is just a way to convert the compiled DFA to a regex, which you could then take in place of the original catenation. The transitions on multiple characters have to be intelligently converted to readable classes like [0-9A-F].
Now suppose we feed it every 0xXXXX string except 0xFFFE.
What that simply means is that the last state transition will not include the F character. In that state, if the next input character is F, the machine errors out.
I'm sure there are issues with this idea that have to be solved. It's a famous fact of DFA construction that a case insensitive match like "[Ff][Oo][Oo]..." leads to an exponential explosion of states.