Tirage à pile ou face de mots de Fibonacci Original Research Article

In this paper, we give a semi-algorithm to sample uniformly at random from the Fibonacci language L=ε+La+Lbb. It needs a uniform bit generator and the average complexity is linear. We show that we can transform this semi-algorithm to a true algorithm still with a linear complexity. Finally, we discuss a generalization to a class of regular languages. Résumé Dans cet article, nous donnons un semi-algorithme qui permet dʹengendrer de façon aléatoire et rigoureusement uniforme un mot du langage de Fibonacci, L=ε+La+Lbb. Il utilise un générateur uniforme de bits et la complexité moyenne en temps et en espace est linéaire. Nous montrons comment transformer ce semi-algorithme en algorithme à terminaison assurée, tout en gardant une complexité linéaire en moyenne. Enfin, on donne une famille de langages rationnels pour lesquels notre méthode sʹapplique.