1
$\begingroup$

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

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.

$\endgroup$

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.