6
$\begingroup$

Given a fixed regular language R, what is the complexity of generating all members of R with length at most $n$? Suppose some reasonable model (RAM with $n$-bit words?) and a write-only output tape. The list should be in length-lexicographical order.

I'm interested in the answer in terms of the output as well as the input. (If R = Σ* then you can't improve on $O(|\Sigma|^n)$ but it only takes time linear in the output.)

$\endgroup$
13
$\begingroup$

There are several recent papers that address your question, e.g.:

Margareta Ackerman and Jeffrey Shallit. Efficient Enumeration of Regular Languages. Conference on Implementation and Application of Automata (CIAA) , Lecture Notes in Computer Science, 4783, Springer-Verlag, Berlin Heidelberg, pp. 226-241, 2007.

Margareta Ackerman and Erkki Makinen. Three New Algorithms for Regular Language Enumeration, Computing and Combinatorics: 15th Annual International Conference (COCOON) , Lecture Notes in Computer Science 5609, Springer-Verlag, Berlin Heidelberg, pp. 178-191, 2009.

You can get these two papers from here.

$\endgroup$
0
1
$\begingroup$

Well, you just need to consider the finite automaton corresponding to the language as a directed graph and output the BFS tree of length $n$ starting from the initial state. This algorithm should take linear time in the output length.

$\endgroup$
0

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.