Random Generation for Finitely Ambiguous Context-free Languages
Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini · RAIRO - Theoretical Informatics and Applications · 2001
We prove that a word of length n from a finitely ambiguous context-free language can be generated at random under uniform distribution in O(n2 log n) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time 1-NAuxPDA with polynomially bounded ambiguity.