A Quasi-polynomial-time Algorithm for Sampling Words from a Context-Free Language
Vivek K. Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, Steve Mahaney · Information and Computation · 1997
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∩Σnof 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.