Zufällige Wörter von Grammatik erstellen

Question

ein bisschen Kontext

Ich habe einen Parser für eine Grammatik geschrieben, und zu Testzwecken bekam ich mit der Idee, einige zufällige Eingänge zu erzeugen. Die Grammatik, mit denen ich befasst hatte, war in dieser Frage viel komplizierter, in dieser Frage, in der ich "minimales Arbeitsbeispiel" für die Einfachheit halte. Und natürlich bin ich in der Lage, das Thema, das ich mit einem Bündel trivialer Heuristiken konfrontiert habe, vermeiden, aber die Frage macht mich wirklich wundern.

Das Problem

Angenommen, wir haben eine typische kontextfreie Grammatik für arithmetische Ausdrücke von $ +, * $ , Klammern und Ganzzahlliteratur:

$$ e \ longrightarrow f ("+" f) ^ * $$ $$ f \ longrightarrow T ("*" t) ^ * $$ $$ t \ longrightarrow Int | "(" E ")" $$

Es ist einfach, einen Staathforward-Algorithmus zum Erzeugen von zufälligen Wörtern durch diese Grammatik zu implementieren: Wir implementieren ein separates Verfahren für jeden Nonterminal. Wenn ein Nonterminal mehrere Produktionsregeln (als $ T $ tut) hat, wählen wir eine Produktionsregel aus, indem Sie eine Münze werfen. Wenn Regel Kleene-Stern enthält (z. B. $ ("+" f) ^ * $ ) werfen wir auch eine Münze und erstellen Null oder eine Wiederholung (sicher, dass wir irgendwelche auswählen könnten Zufällige Ganzzahl $ k \ geq0 $ und generieren $ K $ Wiederholungen, aber für die Einfachheit können wir uns auf die einfachste Version dieses Verfahrens). Hier bekommen wir:

generasacodicetagpre.

Eine Aufrufung von generate_e () ergibt einen zufälligen Ausdruck.

was könnte schief gehen? Es stellt sich heraus, dass die Ausführung dieses Verfahrens an der realen Maschine häufig mit Stapelüberlauf endet. Natürlich haben wir technisch hier eine Möglichkeit der endlosen Rekursion, aber meine Intuition hat mir gesagt, dass die Wahrscheinlichkeit der Erreichung der Erreichung der Rekursionsentiefe $ K $ abklingt exponentiell mit zunehmender $ K $ , daher tiefe Niveaus zu bekommen (sagen wir sagen, 1000) ist fast unmöglich. Anscheinend offenbart ein paar aufeinanderfolgende Läufe, dass die Prozedur problemlos Tiefe von vielen Tausenden erreichen kann (nach Tiefe ich meine maximale Anzahl von Verfahrensanrufen, die der Stapel gleichzeitig enthält).

Ich bin Curios, wie man diese empirische Tatsache formalisiert. Ich möchte entweder eine Formel für $ P (Tiefe= k) $ oder eine asymptotische Annäherung davon oder eine Ungleichung, die den rechten Rückenschwanz von CDF unten begrenzt (so etwas wie $ P (Tiefe> 1000)> 0,05 $ )

mein Versuch

Ich habe versucht, eine Formel für $ P (Tiefe= k) $ :

Lassen Sie uns $ P (Tiefe= k) $ als $ p_e (k) $ . Wir definieren auch ähnliche Werte für generate_f () und generate_t () - $ p_f (k) $ und $ p_t (k) $ sichtlich.

eindeutig ( else zweig von generate_t ), $$ p_t (1)=frac {1} {2} $$ und für $ k> 1 $ ( dann zweig) $$ P_t (k)=frac {1} {2} p_e (k - 1) $$

in Bezug auf $ p_f (k) $ , können wir entweder else -Alteil ausführen, und es gibt Begriffe $$ \ Frac {1} {2} p_t (k - 1) $$ , oder dann Ast, was gibt ein bisschen komplizierter, ein $$ \ frac {1} {2} \ sum _ {(x, y) | Max (x, y)= k - 1} {p_t (x) p_t (y)} $$ dh $$ p_f (k)=frac {1} {2} (p_f (k - 1) + \ sum _ {(x, y) | max (x, y)= k - 1} {p_t (x) p_t (y)}) $$

Schließlich ist die Formel für $ p_e (k) $ fast das gleiche wie für $ p_f (f) $ $ , müssen wir nur $ p_t (x) $ mit $ p_f (x) $ .

Jetzt können wir einige Werte von $ p_e (k) $

berechnen

\ beginnen {Array} {| R | R |} \ HLY K & P_E (k) & p_e (k) \ text {in dezimal} & p_e (k) \ Text {von Monte-Carlo} \\ \ HLY 3 & \ FRAC {33} {128} & \ caPr0.257812 & \ caPr0.2527 \\ \ hline 6 & \ frac {4448787585} {34359738368} & \ ca. ca. ca.0.129477 \ \ ca. \ frac {140803917577471540388216180518131514971222305} {178405961588244985132285746181186892047843328 \ ca. \ ca. ca. ca. \ ca. ca. \ ca. \ ca. \ ca. \ text {the fraction ist zu lang} & \ ca. ca. ca. ca. \ ca. ca. \ ca. ca. ca. ca. \ ca. ca. \ ca. ca. ca. \ ca.0.0530 \\ \ hline \ ende {array}

Wie wir sehen können, scheinen die wiederkehrenden Formeln wahr zu sein, aber weder sie geben mir keinen Einblick in das asymptotische Verhalten von $ p_e (k) $ , noch die Erste Werte geben einen Hinweis auf der Formel in geschlossener Form.

Jede Hilfe würde geschätzt werden.

Answer 1

Ihr Prozess ist ein Lehrbuchbeispiel von einem Verzweigungsprozess . Beginnend mit einem $ E $ , haben wir einen erwarteten 3/2 $ viele $ F $ S, $ 9/4 $ Viele $ T $ s , und so $ 9/8 $ Viele verbleibende $ E $ s in Erwartung. Da $ 9/8> 1 $ nicht verwunderlich ist, dass Ihr Prozess oft nicht beendet wurde.

Um weitere Informationen zu gewinnen, müssen wir die genaue Verteilung der Anzahl der Anzahl der $ E $ -offsprings kennen, die von der folgenden Erzeugungsfunktion angegeben ist (siehe das Wikipedia-Artikel verknüpft mit oben): $$ h (z)=frac {33} {128} + \ frac {7} {16} z + \ frac {15} {64} z ^ 2 + \ frac {1} {16} z ^ 3 + \ frac { 1} {128} z ^ 4. $$ Dies bedeutet, dass die Extinktionswahrscheinlichkeit $ d \ ca. 0,717778143742483 $ (durch Lösen $ H (Z)= Z $ ). Dies ist eine obere Grenze an der Wahrscheinlichkeit, dass Ihr Verfahren endet.

Wir können Ihre Nummern problemlos wiederherstellen, indem er Iterates von $ H $ berücksichtigt. Die Wahrscheinlichkeit, dass der Prozess in 3K $ Schritte endet, ist $ h ^ {(k)} (0) $ . So berechnen $ h (0), h (h (0)) - h (0), h (h (h (h (0))) - h (h (0)) $ usw. wiederherstellen wir die Figuren in Ihrem Tisch wieder.

wenn $ k $ groß ist, $ h ^ {(k)} (0) \ ca. d $ < / span>. Wir können $ H '(D) \ ca. 0.882115879977412 $ berechnen. Wir haben $$ \ frac {d - h ^ {(k)} (0)} {d - h ^ {(k-1)} (0)}= \ frac {h (d) - h (h ^ {(k-1)} (0))} {d - h ^ {(k-1)} (0)} \ ca. h '(d). $$ Es folgt dem $$ d - h ^ {(k)} (0) \ propto h '(d) ^ k. $$ Daher ist die Wahrscheinlichkeit, dass der Prozess in genau 3K $ Schritte endet $$ 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. $$ Im Empirical können wir überprüfen, ob die Konstante der Verhältnismäßigkeit grob ist, in groblicher Math-Container "> $ 0.0248011196615094 $ .

Answer 2

As Yuval hat darauf hingewiesen, dass diese Art und Weise, dass diese Weise zufällig rekursive Datenstrukturen generiert ist (üblicherweise) mit einer unendlichen erwarteten Größe.

Es gibt jedoch eine Lösung für das Problem, mit der man die rekursiven Entscheidungen so wiegen, dass die erwartete Größe innerhalb eines bestimmten endlichen Intervalls liegt: Boltzmann-Sampler . Sie basieren auf der kombinatorischen Erzeugungsfunktion der Struktur und stammen aus der Kombinationstheorie. Für praktische Implementierungen benötigen Sie jedoch nicht die theoretischen Teile. Eine gute programmatische Einführung in Haskell kann gefunden werden in Brent YorReys Blog . Wenn Sie (oder entschlüsseln) HASKELL lesen können, ist der Portieren der Annäherung an Ihre eigene Datenstruktur nicht zu schwierig.

Als Beispiel dafür, wie eine Ableitung wie Ihr Innerhalb dieses Rahmens aussieht, lesen Sie zählen und generieren Begriffe im binären Lambda-Kalkül von Grygiel & Lescanne (Spoiler: Es ist eine überraschende Menge an komplexer Analyse).