<p>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.</p>

CC BY-SA 3.0
2011-08-19T05:43:41.190Z
2011-08-19T05:43:41.190Z
Mahdi Cheraghchi
<p>There are several recent papers that address your question, e.g.:</p>

<p>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.</p>

<p>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.</p>

<p>You can get these two papers from <a href="http://www.cs.uwaterloo.ca/~mackerma/">here</a>.</p>

CC BY-SA 3.0
2011-08-19T07:36:37.237Z
2011-08-19T07:36:37.237Z
Hermann Gruber
<p>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.</p>

<p>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.)</p>

<ds.algorithms><co.combinatorics><fl.formal-languages><regular-language>
Generating all instances of a regular language up to a certain length
Charles
# Generating all instances of a regular language up to a certain length

(Asked by: username_0 on 2011-08-19)

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

**Tags:** ds.algorithms, co.combinatorics, fl.formal-languages, regular-language

---

## 2 answers

### Answer by username_2 on 2011-08-19. Score: 13 | Accepted answer

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](http://www.cs.uwaterloo.ca/~mackerma/).


---

### Answer by username_1 on 2011-08-19. Score: 1

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.


---

