Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$. I want to explore $M$, i.e., visit every state of $M$, or as many states as possible. Unfortunately, I'm not given $M$; I only have the ability to send inputs to $M$.
In particular, what I can do is specify some input strings $x,y,\dots \in \Sigma^*$. The string $x$ will drive $M$ down some path, namely, down the sequence of states $s_0,s_1,s_2,\dots$ where $s_{i+1} = \delta(s_i,x_i)$. I can specify as many input strings as I want.
The cost to me is the sum of the lengths of the input strings. In other words, each transition costs me \$1.
The benefit to me is the fraction of $M$'s states that are visited at least once in response to at least one of these input strings.
I have complete freedom to choose the set of input strings, but I am not given any feedback (I can't see the sequence of states that $M$ follows, I don't learn when I've visited a new state, etc.). I'm hoping to get as much coverage of $M$'s statespace as possible.
How should I choose the set of input strings to maximize the coverage while minimizing the cost? For instance, given a fixed budget, what's the best set of input strings that will give the best benefit? Is there a reasonable strategy, or any theory to help guide the choice of input strings?
Of course, I realize that the worst-case coverage, taken over all possible DFAs, might be very poor. But I would be satisfied with any approach that one can argue is close to optimal, in any meaningful sense. For instance, maybe one metric might be to use a regret ratio, where the regret of strategy 1 compared to strategy 2 is the maximum, over all DFA's $M$, of the benefit of strategy 2 on $M$ divided by the benefit of strategy 1 on $M$. Or maybe you can suggest some other way to formulate this in a principled way that admits an interesting solution. I'm open to suggestions about how to formulate the problem in a way that permits analysis.
If it's helpful, I'll promise that the alphabet is small (say, $|\Sigma| \le 10$), the number of states is not too large (say, $|S| \le 1000$), and the diameter of the graph is small (say, at most 10).
I'm also interested in the variant where $M$ is a NFA instead of a DFA, but I thought I'd start with the simpler case.
This is an attempt at an application of theory to practice. The application is randomized testing of UI-driven applications, where we think of the application as a DFA and the inputs represent user actions (e.g., tapping on a particular portion of the screen). The problem above is an idealization of the problem where we don't get any feedback as we go (which is motivated by the fact that it's not trivial to observe anything reliable about the state of the application).
