FA State function
A DFA can be represented by a very sparse table. Though in practice, this is not a good way because we often want to define values in ranges and entering each value in the range is wasteful
Safe Approach
A simple way that will work efficiently is to store the data in a sorted listed where the index is the state then the start of the range and the value is the end of the range and the output state.
Trees
For the most part, state IDs do not matter so long as they are consistent. We may also want all the output states to have some identifier like having the first bit set to one. It may be even better is we can get all the output states below a specific value and with some target density so that they can be efficiently mapped with an array.
We can form a tree where each branch node contains some low cost check and each leaf node contains a value.
Merging
The way to pick up efficiency is to merge transitions. For instance if state A in range a:b goes to state C and state B in range c:d also goes to C, if we can find a check that matches both those inputs and outputs C, that can be a single node. If that's not possible, it may be possible to find something that is true for all those values, plus some additional values that can be checked against another check.
A more complex merge would be one where A in range a:b goes to state X and state B in range c:d goes to Y, it may be possible to find an operation that produces the correct outputs.
To make this possible, we may also need to split ranges. Say the input is limited to a byte. Something in the range 100 to 150 (01100100 to 10010110), there are no constant leading bits. Defining two ranges as 100 to 127 (01100100 to 01111111) and 128 to 150 (10000000 to 10010110) gives three leading bits. This could be further broken down if necessary, for instance 100 to 111 (01100100 to 01101111) and 112 to 127 (01110000 to 01111111) which gets 4 leading bytes. This is valuable because it is easy to create binary operations that will work on those leading bits.