I&C Journal 1997 Journal Article
A Quasi-polynomial-time Algorithm for Sampling Words from a Context-Free Language
- Vivek Gore
- Mark Jerrum
- Sampath Kannan
- Z. Sweedyk
- Steve Mahaney
A quasi-polynomial-time algorithm is presented for sampling almost uniformly at random from then-slice of the languageL(G) generated by an arbitrary context-free grammarG. (Then-slice of a languageLover an alphabetΣis the subsetL∩Σ n of words of length exactlyn.) The time complexity of the algorithm isε −2(n |G|) O(log n)where the parameterεbounds the variation of the output distribution from uniform, and |G| is a natural measure of the size of grammarG. The algorithm applies to a class of language sampling problems that includes slices of context-free languages as a proper subclass. For the restricted case of homogeneous languages expressed by regular expressions without Kleene-star, a truly polynomial-time algorithm is presented.