### Z Sweedyk

### University of Pennsylvania

### A quasi-polynomial-time algorithm for sampling words from a context-free language

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.