We give a quasi-polynomial-time algorithm for sampling almost uniformly at random from the n-slice of the language L generated by an arbitrary context-free grammar. (The n-slice of L is the words in L of length exactly n.) For the restricted case of homogeneous languages expressed by regular expressions without Kleene-star, a truly polynomial-time algorithm is presented.

This is joint work with Vivek Gore, Mark Jerrum, Sampath Kannan, and Steve Mahaney.