Random generation of words in an algebraic language in linear binary space

We show that, for every unambiguous context-free language L, a uniform random word of length n in L can be generated in O(n log n) time by using O(n) binary space. The algorithm is based on a general technique proposed by Flajolet et al. (1993) for the random generation of combinatorial structures