Générer des mots aléatoires par grammaire

Question

Un peu de contexte

J'écris un analyseur pour une grammaire et à des fins de test, je propose une idée de générer des entrées aléatoires. La grammaire que je traitais était beaucoup plus compliquée, dans cette question, j'ai présenté un "exemple de travail minimal" pour la simplicité. Et bien sûr, je suis capable d'éviter la question à laquelle je suis confronté en utilisant un tas d'heuristiques triviales, mais la question me fait vraiment me demander.

Le problème

Supposons que nous ayons une grammaire typique sans contexte pour les expressions arithmétiques de $ +, * $ , crochets et littéraux entier:

$$ e \ longrightarrow f ("+" f) ^ * $$ $$ f \ longrientarrow t ("*" t) ^ * $$ $$ t \ longrightarrow int | "(" e ")" $$

Il est facile de mettre en œuvre un algorithme Staighforward pour générer des mots aléatoires par cette grammaire: nous mettons en œuvre une procédure distincte pour chaque non-déterminant. Si un non-déterminant a plusieurs règles de production (comme $ t $ fait), nous choisissons une règle de production en jetant une pièce de monnaie. Si la règle contient une étoile kleène (par exemple $ ("+" f) ^ * $ ), nous jetons également une pièce de monnaie et génère zéro ou une répétition (sûr que nous pourrions choisir tout aléatoire entier $ k \ geq0 $ et générer $ k $ répétitions, mais pour la simplicité, nous nous concentrerons sur le version la plus simple de cette procédure). Voici ce que nous obtenons:

generate_E():
    if coin_toss():
        return generate_F() + "+" + generate_F()
    else:
        return generate_F()

generate_F():
    if coin_toss():
        return generate_T() + "*" + generate_T()
    else:
        return generate_F()

def generate_T():
    if coin_toss():
        return "(" + generate_E() + ")"
    else:
        return random_integer()

Une invocation de générate_e () donne une expression aléatoire.

Qu'est-ce qui pourrait aller mal? Il s'avère que l'exécution de cette procédure sur la vraie machine se termine par un débordement de pile assez souvent. Bien sûr, techniquement, nous avons une possibilité de récursion sans fin, mais mon intuition me disait que la probabilité d'atteindre la profondeur de la récursivité $ k $ se désintègre de manière exponentielle avec l'augmentation de $ K $ , donc des niveaux profonds (disons, 1000) est presque impossible. Apparemment, quelques courses consécutives révèlent que la procédure peut facilement atteindre la profondeur de plusieurs milliers (en profondeur, je veux dire nombre maximum d'appels de procédure que la pile contient simultanément).

Je suis Curios Comment formaliser ce fait empirique. Je veux soit une formule pour $ p (profondeur= k) $ ou une approximation asymptotique de celui-ci, ou une inégalité de la queue droite de CDF ci-dessous (quelque chose comme $ p (profondeur> 1000)> 0.05 $ )

Ma tentative

J'ai essayé de trouver une formule pour $ p (profondeur= k) $ :

Notons $ p (Profondeur= K) $ comme $ p_e (k) $ . En outre, nous définissons des valeurs similaires pour generate_f () et generate_t () - $ p_f (k) $ et $ p_t (k) $ respectueux.

Clairement ( el> branche de generate_t ), $$ p_t (1)=frac {1} {2} $$ et pour $ k> 1 $ ( puis branche) $$ P_t (k)=frac {1} {2} p_e (k - 1) $$

concernant $ p_f (k) $ , nous pouvons soit exécuter el> sino suck, et il donne le terme $$ \ frac {1} {2} p_t (k - 1) $$ ou puis branche, ce qui donne un peu plus compliqué one $$ \ frac {1} {2} \ Somme _ {(x, y) | max (x, y)= k - 1} {p_t (x) p_t (y)} $$ ie $$ p_f (k)=frac {1} {2} (p_f (k - 1) + \ somme _ {(x, y) | max (x, y)= k - 1} {p_t (x) p_t (y)}) $$

Enfin, la formule de $ p_e (k) $ est presque la même que pour $ p_f (f) $ $ , il suffit de remplacer $ p_t (x) $ avec $ p_f (x) $ .

Maintenant, nous pouvons calculer certaines valeurs de $ p_e (k) $

\ commencez {array} {| r | r |} \ hline k & p_e (k) & p_e (k) \ texte {en décimal} & p_e (k) \ Texte {by Monte-Carlo} \\ \ hille 3 & \ frac {33} {128} & \ environ 0.257812 & \ environ 6 & \ frac {4448787585} {34359738368} & \ environ-129477 & \ approx0.1282 \\ \ hline 9 & \ frac {} {14080391757747154038821618051813151497122305 178405961588244985132285746181186892047843328} & \ approx0.078923 & \ approx0.0761 \\ \ hline 12 & \ text {la fraction est trop long} et \ approx0.053213 & \ environ0.0530 \\ \ hline \ fin {array}

Comme on peut le constater, les formules récurrentes semblent être vraies, mais elles ne me donnent pas une perspicacité sur le comportement asymptotique de $ p_e (k) $ , ni le Les premières valeurs donnent un indice sur la formule sous forme fermée.

Toute aide serait appréciée.

Answer 1

Votre processus est un exemple de manuel d'un processus de ramification . En commençant par une $ E $ , nous avons une attente $ 3/2 $ beaucoup $ F $ s, 9/4 $ beaucoup $ t $ s , et donc 9/8 $ beaucoup restant $ e $ s dans l'attente. Puisque 9/8 $> 1 $ , il n'est pas surprenant que votre processus n'a souvent pas terminé.

Pour gagner plus d'informations, nous devons connaître la distribution exacte du nombre de $ e $ -Offsprings, qui est donné par la fonction génératrice suivante (voir la Article Wikipedia lié ci-dessus): $$ h (z)=frac {33} {128} + \ frac {7} {16} z + \ frac {15} {64} z ^ 2 + \ frac {1} {16} z ^ 3 + \ frac { 1} {128} z ^ 4. $$ Cela implique que la probabilité d'extinction est $ d \ environ 0,717778143742483 $ (en résolvant $ h (z)= z $ ). Ceci est une limite supérieure sur la probabilité que votre procédure se termine.

Nous pouvons facilement récupérer vos numéros en considérant itétites de $ h $ . La probabilité que le processus se termine dans pas de $ 3k $ est $ h ^ {(k)} (0) $ . Tellement informatique H (0), H (H (0)) - H (0), H (H (h (0))) - H (H (0)) $ et ainsi de suite, nous récupérons les chiffres de votre table.

quand $ k $ est grand, $ h ^ {(k)} (0) \ environ d $ < / span>. Nous pouvons calculer $ h '(d) \ environ 0,882115879977412 $ . On a $$ \ frac {d - h ^ {(k)} (0)} {d - h ^ {(k-1)} (0)}= \ frac {h (d) - H (h ^ {(k-1)} (0))} {d - h ^ {(k-1)} (0)} \ env. D). $$ Il s'ensuit que $$ d - h ^ {(k)} (0) \ propto h '(d) ^ k. $$ Par conséquent, la probabilité que le processus se termine exactement 3k $ étapes est $$ h ^ {(k)} (0) - h ^ {(k-1)} (0)= [D - H ^ {(K-1)} (0)] - [D - H ^ {((K)} (0)] \ Propto H '(D) ^ {K-1} - H' (D) ^ k \ propto h '(d) ^ k. $$ Empiriquement, nous pouvons vérifier que la constante de proportionnalité est grossièrement 0,0248011196615094 $ .

.

Answer 2

Comme Yuval l'a noté, cette façon de générer de manière aléatoire des structures de données récursives est connue (généralement) finit par une taille attendue infinie.

Il y a cependant une solution au problème, qui permet de peser les choix récursif de manière à ce que la taille attendue se situe dans un certain intervalle fini: Sampliers de Boltzmann . Ils sont basés sur la fonction de génération combinatoire de la structure et proviennent de la théorie des espèces combinatoires. Pour des implémentations pratiques, vous n'avez pas besoin des parties théoriques, cependant. Une bonne introduction programmatique à Haskell peut être trouvée dans le blog de Brent Youringy . Si vous pouvez lire (ou déchiffrer) HASKELL, le portage de l'approche de votre propre structure de données n'est pas trop difficile.

Comme exemple de la manière dont une dérivation comme la vôtre regarde dans ce cadre, lisez Compter et générer Termes dans le calcul binaire Lambda par Grygiel & LaCunne (Spoiler: C'est une quantité surprenante d'analyse complexe).