On the circuit complexity of random generation problems for regular and context-free languages

We study the circuit complexity of generating at random a word of length n from a given language under uniform distribution. We prove that, for every language accepted in polynomial time by 1-NAuxPDA of polynomially bounded ambiguity, the problem is solvable by a logspace-uniform family of probabilistic boolean circuits of polynomial size and O(log2 n) depth. Using a suitable notion of reducibility (similar to the NC1-reducibility), we also show the relationship between random generation problems for regular and context-free languages and classical computational complexity classes such as DIV, L and DET.