Generando parole casuali per grammatica

Question

un po 'di contesto

Stavo scrivendo un parser per una grammatica e per i fini di test, ho intenzione di generare alcuni input casuali. La grammatica con cui ho a che fare è stato molto più complicato, in questa domanda ho presentato "esempio di lavoro minimo" per semplicità. E naturalmente, sono in grado di evitare il problema che ho affrontato usando un gruppo di euristici banale, ma la domanda mi fa davvero meravigliare.

il problema

Supponiamo di avere una tipica grammatica senza contesto per le espressioni aritmetiche di $ +, * $ , parentesi e lettele interi:

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

È facile implementare un algoritmo Staighforward per generare parole casuali da questa grammatica: implementiamo una procedura separata per ciascun nonterminale. Se un nonterminale ha più regole di produzione (come $ T $ fa), scegliamo una regola di produzione lanciando una moneta. Se la regola contiene la stella di Kleene (ad es. $ ("+" f) ^ * $ ), scendiamo anche una moneta e generare zero o una ripetizione (certo che potremmo scegliere Integer casuale $ k \ geq0 $ e generare $ k $ ripetizioni, ma per semplicità ci concentreremo sul versione più semplice di questa procedura). Ecco cosa otteniamo:

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()

.

Un'invocazione di GeneraTE_E () produce un'espressione casuale.

Cosa potrebbe andare storto? Si scopre che l'esecuzione di questa procedura sulla vera macchina termina con lo stack overflow abbastanza spesso. Naturalmente, tecnicamente qui abbiamo la possibilità di una rifacissione infinita, ma la mia intuizione mi stava dicendo che la probabilità di raggiungere la profondità di ricorsione $ k $ decade esponenzialmente con l'aumento della classe $ k $ , quindi ottenere livelli profondi (diciamo, 1000) è quasi impossibile. Apparentemente, alcune piste consecutive rivelano che la procedura può facilmente raggiungere la profondità di molte migliaia (per profondità, intendo il numero massimo di chiamate di procedura, la pila contiene simultaneamente).

Sono curios come formalizzare questo fatto empirico. Voglio una formula per $ p (profondità= k) $ o un'approssimazione asintotica di esso, o una disuguaglianza delimitare la coda destra del CDF sottostante (qualcosa come < class="Math-Container"> $ P (profondità> 1000)> 0,05 $ )

il mio tentativo

Ho provato a trovare una formula per $ p (profondità= k) $ :

Denniamo $ P (profondità= k) $ come $ p_e (k) $ . Inoltre, definiamo valori simili per Generate_f () e Generate_t () - $ p_f (k) $ e $ p_t (k) $ rispettatamente.

Chiaramente ( Else Branch of Generate_t ), $$ p_t (1)=frac {1} {2} $$ e per $ k> 1 $ ( quindi ramo) $$ P_t (k)=frac {1} {2} p_e (k - 1) $$

Per quanto riguarda $ p_f (k) $ , possiamo eseguire altro ramo, e dà il termine $$ \ frac {1} {2} p_t (k - 1) $$ o quindi ramo, cosa dà un po 'più complicato una $$ \ frac {1} {2} \ Sum _ {(x, y) | max (x, y)= k - 1} {p_t (x) p_t (y)} $$ IE $$ p_f (k)=frac {1} {2} (P_F (k - 1) + \ Sum _ {(x, y) | max (x, y)= k - 1} {p_t (x) p_t (y)}) $$ .

Infine, la formula per $ p_e (k) $ è quasi la stessa di $ p_f (f) $ , dobbiamo solo sostituire $ p_t (x) $ con $ p_f (x) $ .

Ora, possiamo calcolare alcuni valori di $ p_e (k) $

\ begin {array} {| r | r |} {| r | r |} \ hline k & p_e (k) & p_e (k) \ testo {in decimale} e p_e (k) \ testo {di Monte-Carlo} \\ \ \ hline 3 & \ frac {33} {128} & \ circa 60.257812 & \ circa 6 e \ frac {4448787585} {34359738368} & \ circa 60.129477 & \ circa 9.1282 \\ \ \ hline 9 & \ frac {14080391757747154039175774715403882161805181511805181511805181511805181511805181518882445961588244985188244985158824498518824498511885746181886857461818868574618118685746181886857461818868920478433328} & \ circa 6 & \ text {la frazione è troppo lunga} & \ circa-0.053213 \ circa 40.0530 \\ \ hline \ end {array}

Come possiamo vedere, le formule ricorrenti sembrano essere vere, ma né mi danno un'intuizione sul comportamento asintotico di $ P_E (K) $ , né il I primi valori danno un indizio sulla formula in forma chiusa.

Qualsiasi aiuto sarebbe apprezzato.

Answer 1

Il tuo processo è un esempio di libro di testo di un processo di ramificazione . A partire da una classe $ e $ , abbiamo una prevista $ 3/2 $ Molte $ F $ s, $ 9/4 $ Molti $ T $ s e così $ 9/8 $ molti restanti $ e $ s in attesa. Dal momento che $ 9/8> 1 $ , non sorprende che il tuo processo spesso non sia riuscito a terminare.

Per ottenere ulteriori informazioni, dobbiamo conoscere la distribuzione esatta del numero di $ e $ -offsprings, che è fornita dalla seguente funzione generatrice (vedi Articolo di Wikipedia collegato a sopra): $$ h (z)=frac {33} {128} + \ frac {7} {16} z + \ frac {15} {64} z ^ 2 + \ frac {1} {16} z ^ 3 + \ frac { 1} {128} z ^ 4. $$ Ciò implica che la probabilità di estinzione è $ d \ circa 0,717778143742483 $ (risolvendo $ h (z)= z $ ). Questo è un limite superiore sulla probabilità che la procedura termina.

Possiamo facilmente recuperare i tuoi numeri considerando iterati di $ h $ . La probabilità che il processo termina in $ 3k $ passaggi è $ h ^ {k)} (0) $ . Così computing $ h (0), h (h (0)) - h (0), h (h (h (0))) - h (h (0)) $ E così via, recuperamo le figure nella tabella.

Quando $ k $ è grande, $ h ^ {k)} (0) \ circa D $ < / span>. Possiamo calcolare $ h '(d) \ circa 0,882115879977412 $ . Abbiamo $$ \ frac {d - h ^ {(k)} (0)} {d - h ^ {(k-1)} (0)}= \ frac {h (d) - h (h ^ {(k-1)} (0))} {d - h ^ {(k-1)} (0)} \ circa H '(D). $$ Ne consegue che $$ D - H ^ {(K)} (0) \ Propto h '(d) ^ k. $$ Pertanto la probabilità che il processo termina in modo esatto $ 3k $ passaggi è $$ 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. $$ Empiricamente, possiamo verificare che la costante proporzionalità sia all'incirca $ 0,0248011196615094 $ .

Answer 2

AS YUVAL ha notato, questo modo di generare casualmente la generazione di strutture di dati ricorsivi è nota a (di solito) finisce con una dimensione prevista infinita.

C'è, tuttavia, una soluzione al problema, che consente di pesare le scelte ricorsive in modo tale che la dimensione prevista si trova all'interno di un determinato intervallo finito: campionatori di Boltzmann . Si basano sulla funzione generatrice combinatoria della struttura e proviene dalla teoria delle specie combinatoriali. Per implementazioni pratiche, non hai bisogno delle parti teoriche, però. Una buona introduzione programmatica in Haskell può essere trovata nel blog di Brent Yorgey . Se riesci a leggere (o decifrare) Haskell, porting l'approccio alla propria struttura dei dati non è troppo difficile.

come esempio per come una derivazione come il tuo guarda all'interno di quel framework, leggi contando e generando Termini nel calcolo della lambda binaria di Grygiel & Lescanne (spoiler: è una quantità sorprendente di analisi complessa).