Generando palabras aleatorias por gramática.

Question

un poco de contexto

Estaba escribiendo un analizador para una gramática, y para fines de prueba, me siento con la idea de generar algunas entradas al azar. La gramática con la que estaba lidiando fue mucho más complicada, en esta pregunta presenté "Ejemplo de trabajo mínimo" para la simplicidad. Y, por supuesto, soy capaz de evitar el problema que enfrenté con un montón de heurísticas triviales, pero la pregunta realmente me hace preguntarme.

El problema

Supongamos que tenemos una gramática típica libre de contexto para expresiones aritméticas de $ +, * $ , paréntesis y literales enteros:

$$ E \ LONGRIGHTARROW F ("+" F) ^ * $$ $$ F \ LONGRIGHTARROW T ("*" t) ^ * $$ $$ t \ longightarrow int | "(" e ")" $$

Es fácil implementar un algoritmo de Staighforward para generar palabras aleatorias por esta gramática: implementamos un procedimiento separado para cada antiérmino. Si un antiérmico tiene múltiples reglas de producción (como $ t $ hace), elegimos una regla de producción lanzando una moneda. Si la regla contiene la estrella de Kleene (por ejemplo, $ ("+" F) ^ * $ ), también lanzamos una moneda y genemos cero o una repetición (seguro que podríamos elegir cualquier Entero aleatorio $ k \ geq0 $ y genera $ k $ repeticiones, pero por simplicidad nos centraremos en el Versión más sencilla de este procedimiento). Aquí está lo que obtenemos:

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

Una invocación de generate_e () produce una expresión aleatoria.

¿Qué podría salir mal? Resulta que la ejecución de este procedimiento en la máquina real termina con un desbordamiento de pila con bastante frecuencia. Por supuesto, técnicamente aquí tenemos la posibilidad de una recursión interminable, pero mi intuición me estaba diciendo que la probabilidad de alcanzar la profundidad de la recursión $ k $ se desintege de manera exponencial con el aumento de $ K $ , por lo tanto, obtener niveles profundos (digamos, 1000) es casi imposible. Aparentemente, unas pocas carreras consecutivas revelan que el procedimiento puede alcanzar fácilmente la profundidad de muchos miles (por profundidad, quiero decir el número máximo de llamadas de procedimiento, la pila contiene simultáneamente).

Estoy curiosando cómo formalizar este hecho empírico. Quiero una fórmula para $ P (profundidad= k) $ , o una aproximación asintótica de la misma, o una desigualdad límite de la cola derecha de la CDF a continuación (algo así como $ P (profundidad> 1000)> 0.05 $ )

Mi intento

Intenté encontrar una fórmula para $ P (profundidad= k) $ :

Denoticemos $ P (profundidad= k) $ como $ p_e (k) $ . Además, definimos valores similares para generate_f () y generate_t () - $ p_f (k) $ y $ P_T (k) $ respectivamente.

claramente ( otra rama de genera_t ), $$ P_T (1)=frac {1} {2} $$ y para $ k> 1 $ ( luego sucursal) $$ P_T (k)=frac {1} {2} P_E (K - 1) $$

con respecto a $ P_F (k) $ , podemos ejecutar otra cosa , y le da el término $$ \ FRAC {1} {2} P_T (K - 1) $$ , o luego , lo que le da un poco más complicado 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)}) $$

Finalmente, la fórmula para $ p_e (k) $ es casi lo mismo que para $ p_f (f) $ , solo tenemos que reemplazar $ p_t (x) $ con $ p_f (x) $ .

Ahora, podemos calcular algunos valores de $ p_e (k) $

\ comienzan {array} {| r | r |} \ hline k & p_e (k) & p_e (k) \ texto {en decimal} & p_e (k) \ Texto {by Monte-Carlo} \\ \ Hline 3 & \ frac {33} {128} & \ aprox0.257812 & \ aprox0.257812 & \ \ aprox 60.2527 \\ \ hline 6 & \ frac {4448787585} {34359738368} & \ aprox.129477 & \ aprox.1282 \\ \ hline 9 & \ frac {140803917577471540388216180518151797122305} {178405961588244981111158824461811118689204781111186892047843328} & \ aprox0.078923 & \ aprox0.076123 & \ {la fracción es demasiado largo} & \ aprox0.053213 & \ aprox0.0530 \\ \ hline \ end {array}

Como podemos ver, las fórmulas recurrentes parecen ser cieguesas, pero tampoco me dan una idea del comportamiento asintótico de $ p_e (k) $ , ni el Los primeros valores dan una pista en la fórmula en forma cerrada.

Se apreciaría cualquier ayuda.

Answer 1

Su proceso es un ejemplo de libro de texto de una proceso de ramificación . Comenzando con un $ e $ , tenemos un $ 3/2 $ Muchos $ F $ s, $ 9/4 $ Muchos $ t $ s , y así $ 9/8 $ Muchos restantes $ e $ s en la expectativa. Desde $ 9/8> 1 $ , no es sorprendente que su proceso a menudo no haya terminado.

Para obtener más información, necesitamos conocer la distribución exacta del número de $ e $ -offsprings, que se da por la siguiente función de generación (consulte la Artículo de Wikipedia vinculado a lo anterior): $$ h (z)=frac {33} {128} + \ frac {7} {16} Z + \ frac {15} {64} Z ^ 2 + \ frac {1} {16} Z ^ 3 + \ frac { 1} {128} Z ^ 4. $$ Esto implica que la probabilidad de extinción es $ d \ aprox. 0.717778143742483 $ (mediante la solución $ h (z)= z $ ). Este es un límite superior con la probabilidad de que su procedimiento termine.

Podemos recuperar fácilmente sus números considerando los iterados de $ H $ . La probabilidad de que el proceso termine en $ 3k $ Pasos es $ h ^ {(k)} (0) $ . Así que computando $ h (0), h (h (0)) - h (0), h (h (h (h (0))) - H (H (0)) $ y así, recuperamos las figuras en su mesa.

Cuando $ k $ es grande, $ h ^ {(k)} (0) \ aprox d $ < / span>. Podemos calcular $ h '(d) \ aprox 0.882115879977412 $ . Tenemos $$ \ frac {d - h ^ {(k)} (0)} {d - h ^ {(k-1)} (0)}= \ frac {h (d) - h (h ^ {(k-1)} (0))} {d - h ^ {(k-1)} (0)} \ aproximadamente h '(D). $$ Resulta que $$ d - h ^ {(k)} (0) \ propto h '(d) ^ k. $$ Por lo tanto, la probabilidad de que el proceso termine en exactamente $ 3K $ pasos es $$ 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. $$ Empíricamente, podemos verificar que la constante de proporcionalidad sea aproximadamente $ 0.0248011196615094 $ .

Answer 2

Como se ha señalado Yuval, se sabe que esta forma de generar estructuras de datos recursivas al azar (generalmente) termina con un tamaño esperado infinito.

Hay, sin embargo, una solución al problema, que permite a uno pesar las opciones recursivas de tal manera que el tamaño esperado se encuentra dentro de un determinado intervalo finito: muestreadores de boltzmann . Se basan en la función de generación combinatoria de la estructura y provienen de la teoría de las especies combinatoriales. Para las implementaciones prácticas, no necesita las partes teóricas. Una buena introducción programática en Haskell se puede encontrar en el blog de Brent Yorgey . Si puede leer (o descifrar) Haskell, la portación del enfoque de su propia estructura de datos no es demasiado difícil.

Como ejemplo para cómo una derivación como la suya se ve dentro de ese marco, lee contando y generando Términos en el cálculo de lambda binario de Grygiel & Lescanne (Spoiler: Es una cantidad sorprendente de análisis complejo).