# 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|}$.
• "succinctly represented as a acyclic DFA" -- oxymoron intended? – Raphael Aug 28 '14 at 12:44

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.