1
$\begingroup$

As the title states I'm trying to write an algorithm that generates accepted strings to an upper bound from a given DFA.

It should not generate more strings than the upper bound n if it contains cyclic patterns, because obviously I can't print an infinite amount of strings, which leads me to my problem.

Machines with finite languages are very straight forward as I can just do a DFS search and traverse through the graph and concatenate all letters that connect the states recursively, but I have no clue how I should deal with infinite language DFAs unless I hardcode a limit on how many times the DFS should traverse states that can potentially lead to cycles.

So my question is; how should go about approaching this problem. Are there any known algorithms (aside from DFS, BFS) that I could use to tackle this task?

Thanks in advance. I tried hard to find similar questions but I couldn't find anything helpful.

Edit: Clarified problem a little bit.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Aug 29 '18 at 18:09
1
$\begingroup$

The simplest one is to generate all strings up to length n and test them against the DFA.

The next option is a Breadth first traversal over the DFA (emitting the string each time you encounter a final state) however this can need a lot of memory. In the worst case all you need to keep all of length n in memory.

Next is a depth first traversal up to length n. Keep a counter of how long the string would be and backtrack when you exceed n.

To instead get the first n strings you run one of the above algorithms with a certain length and if it generates not enough strings you increment n until it does.

$\endgroup$
1
$\begingroup$

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

  1. 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

    • reachable from the start state

    • accepting, or able to reach an accepting state

If that's not guaranteed in the DFAs you're begin given, it is easy to guarantee by detecting and removing useless states.

$\endgroup$
  • $\begingroup$ Hmm, I'm not entirely sure that's why I get stuck on the automata that accepts all strings of (length mod 7) = 0. I think because the automata looks something like: S0->A-z->S1 S0->a-z->S1 S0->0-9->S1 S1->"A-z"->S2 S1->"a-z"->S2 S1->"0-9"->S2 .... S6->"A-z"->S0 S6->"a-z"->S0 S6->"0-9"->S0 So it has to iterate a huuuge amount of strings before even reaching the start state, which is why it gets stuck I think. Is there a way to prevent it from branching so many times without changing back to DFS? $\endgroup$ – wayAboveMyHead Aug 24 '18 at 10:47
  • $\begingroup$ @way: yes, exactly the solution I propose. Just make sure that the work queue in your bfs implementation never has more than limit entries. Maybe I wasn't clear enough in the answer. $\endgroup$ – rici Aug 24 '18 at 13:32
  • $\begingroup$ The limit being the number of strings? The work queue is the number of transitions per state that I should try to go through? Or how do you limit the work queue? $\endgroup$ – wayAboveMyHead Aug 24 '18 at 14:07
  • $\begingroup$ @way: Ok, I rewrote the answer. Good luck with your assignment. $\endgroup$ – rici Aug 24 '18 at 17:06
  • $\begingroup$ Wow thank you so much for the elaborate reply and thanks! I'll get back to it as soon as I can and use your advice! $\endgroup$ – wayAboveMyHead Aug 24 '18 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.