Sampling from a Acyclic Deterministic Finite Automaton Assume you have a finite language $L$ succinctly represented as a acyclic DFA $M$ (models can't be much simpler than that :) ).


  How can we efficiently sample a word from $L$ with uniform distribution?


Note that counting the number of words in $L$ is easily doable in linear time in the size of $M$, which might be useful for the sampling process.



Clarifications:


$L(M)=L$.
$M$ is acyclic (has no loops).
Sampling means you output each word $w\in L$ w.p. $\frac{1}{|L|}$.
Some rough thoughts:

As $M$ is acyclic and deterministic, each word $w$ in $L$ determines a unique path through $M$. Therefore, at each state $q \in Q$, we weight each transition based upon the number of valid subsequent paths (this is the size of the subset of $L$ with a particular prefix). This can be done recursively, and should be linear in the number of transitions.

Then, in order to sample, we can define a function $p: Q\times\Sigma \to R$ that gets us this 'weight' of a particular transition, and use this to define the probability of moving through that transition. At the end of this, rolling a die at each transition should get a normal sample.

I've probably missed something, but it seems like a decent approach.