The essence of this problem is to search the possibly-infinite transition tree induced by the DFA. Each node in this tree consists of a state and a string (the prefix of a recognised sentence). For each possible transition from the state, there is a child node consisting of the target state and the string augmented with the transition character. The target strings are those belonging to nodes whose states are accepting states.
I think this assignment is probably intended to get you to understand recursion with back-tracking, since there is a pretty simple solution: recursively (depth-first) walk the transition tree, failing if the recursion depth reaches the limit on string length. (If strings can be long, you might want to use an explicit stack rather than recursion to avoid stack overflow.)
That is not, in my opinion, the best solution to this problem. I'd use a breadth-first search limited to the number of strings you need to find. However, if you do choose to implement the recursive backtracking solution, I do recommend that you do useless state elimination as suggested by [Note 1]; otherwise, a self-looping dead state (with at least two loops) will produce exponential slow-down during the DFS.
Let's recall that the basic breadth-first algorithm involves the use of a queue of transition tree nodes. We initialise the queue with the root node ($<start, "">$) and then, as long as the queue is non-empty and we have not found enough solutions, we do the following:
1. Remove the first node from the queue
2. If that node has an accepting state, report the string as a solution.
3. Append all possible transitions from that node to the end of the queue.
The result of this algorithm is that solutions will be generated in order by length, shortest strings first.
The problem with breadth-first search, as I gather you discovered through experimentation, is that if the branching factor is high and several transitions are required before an accepting state is found, then the queue expands to an exponential size (and that takes exponential time).
However, not all of the queue is necessary, since the number of target strings is known in advance. If we assume that the DFA has no useless states [Note 1], then every node in the transition tree is either a solution or has at least one solution in its subtree. Consequently, the maximum useful size of the queue is the number of solutions we require. When the queue has reached this size, we just don't do the append. When we find a solution, we can reduce the size limit by one.
Imposing this limit on the queue size removes the possibility of exponential time blow-up, but a naïve implementation no longer guarantees that the solutions found are the shortest solutions. This introduces an inefficiency, and even a possible error (because in pathological cases we might reach the string size limit before finding enough solutions, even though shorter solutions exist).
As a fix, we can track the levels during the BFS walk, reordering the traverse of each level. In this version, we use two queues, one for the current level, from which we pop nodes, and one for the next level, onto which we push newly found nodes. Every time the current queue becomes empty we've finished a level; we then swap the two queues. If both queues are empty, there's nothing more to be done.
Now we're not limited to processing the queue for a level from left-to-right; we can process it as we see fit, as long as we do all of it before moving on to the next node.
For a first approximation, we can ensure that we don't lose any accepting states. When we push a new node onto the next level:
If it is an accepting node, we push it onto the beginning. If the queue is full, we push the new node anyway, popping the last node.
If it is not an accepting node and the queue is not full, we push it at the end.
That still won't guarantee that all shortest strings are produced, but it should be sufficient in most cases. It can be improved by sorting the next-level queue by the minimum distance from each state to an accepting state. The minimum distances for each state can be precomputed with a simple breadth-first search over the DFA, which will also serve to eliminate useless states
Notes
Here I'm using the phrase "useless state" in a possibly non-standard way. By "useless state" I mean a state which does not appear in any transition sequence ending at an accepting state. In other words, for a state to be useful, it must be
If that's not guaranteed in the DFAs you're begin given, it is easy to guarantee by detecting and removing useless states.
