You should just useThe essence of this problem is to search the possibly-infinite transition tree induced by the DFA. Each node in this tree consists of a breadthstate 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 search) 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.)
One potential problemThat is thatnot, in my opinion, the BFS might accumulatebest solution to this problem. I'd use a hugebreadth-first search limited to the number of short non-accepted strings before it generates useful stringsyou need to find. ButHowever, if it is OKyou do choose to assume thatimplement the DFA has norecursive backtracking solution, I do recommend that you do useless state elimination as suggested by [Note 1]; otherwise, a self-looping dead statesstate -(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, for every state therewe 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 some sequence ofbranching factor is high and several transitions which will reachare required before an accepting state --is found, then you can reduce the damage by limiting thequeue expands to an exponential size (and that takes exponential time).
However, not all of the setqueue 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 level tosolution or has at least one solution in its subtree. Consequently, the totalmaximum useful size of the queue is the number of strings you want to generatesolutions we require. When doing thatthe queue has reached this size, you might want to makewe 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 attempt to keep as many different states asinefficiency, and even a possible error (because in pathological cases we might reach the string size limit before finding enough solutions, because if alleven though shorter solutions exist).
As a fix, we can track the strings you keep arelevels 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 statefor the next level, onto which we push newly found nodes. Every time the result set mightcurrent 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 highly biaseddone. Unless you have
Now we're not limited to processing the queue for a huge numberlevel from left-to-right; we can process it as we see fit, as long as we do all of statesit before moving on to the next node.
For a first approximation, we can ensure that should be fairly simplewe 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.
A more sophisticated heuristicWith this modification, we can count the accepting node when we push it onto the next-level queue, rather than just keeping a random collection ofwhen we pop if off the current queue. Counting the accepting node early means that we can terminate the algorithm earlier.
That still won't guarantee that all shortest strings at each levelare produced, wouldbut it should be to startsufficient in most cases. It can be improved by computingsorting the shortest pathnext-level queue by the minimum distance from each non-accepting state to somean accepting state, using the standard all-shortest-paths algorithm. Then atThe minimum distances for each level, youstate can selectbe precomputed with a simple breadth-first search over the set of candidatesDFA, which are closestwill also serve to being acceptedeliminate 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.
