Random generation of words of context-free languages according to the frequencies of letters
Alain Denise, Olivier Roques, Michel Termier · Mathematics and Computer Science · 2000
Let L be a context-free language on an alphabet X={ x 1 ,x 2 ,…, x k } and n a positive integer. We consider the problem of generating at random words of L with re-spect to a given distribution of the number of occurrences of the letters. We consider two alternatives of the problem. In the first one, a vector of natural numbers (n 1 , n 2 ,…,n k ) such that n 1 + n 2 +… + n k = n is given, and the words must be generated uniformly among the set of words of L which contain exactly n i letters x i (1 ≤ i ≤ k). The second alternative consists, given v = (v i ,…, v k ) a vector of positive real numbers such that v i +… + v k = 1, to generate at random words among the whole set of words of L of length n, in such a way that the expected number of occurrences of any letter x i equals nv i (1 ≤i ≤ k), and two words having the same distribution of letters have the same probability to be generated. For this purpose, we design and study two alternatives of the recursive method which is classically employed for the uniform generation of combinatorial structures. This type of “controlled” non-uniform generation can be applied in the field of statistical analysis of genomic sequences. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.