# Generating all instances of a regular language up to a certain length

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

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.