Gerando palavras aleatórias por gramática

Question

Um pouco de contexto

Eu estava escrevendo um analisador para uma gramática e, para fins de teste, tive a ideia de gerar algumas entradas aleatórias.A gramática com a qual estava lidando era muito mais complicada, nesta questão apresentei "exemplo mínimo de trabalho" para simplificar.E, claro, sou capaz de evitar o problema que enfrentei usando um monte de heurísticas triviais, mas a questão realmente me faz pensar.

O problema

Suponha que temos uma gramática livre de contexto típica para expressões aritméticas de $+,*$, colchetes e literais inteiros:

$$E \longrightarrow F(“+”F)^*$$ $$F \longrightarrow T(“*”T)^*$$ $$T\longrightarrow int|“(”E“)”$$

É fácil implementar um algoritmo simples para gerar palavras aleatórias por meio desta gramática:implementamos um procedimento separado para cada não-terminal.Se um não-terminal tiver múltiplas regras de produção (como $T$ faz), escolhemos uma regra de produção lançando uma moeda.Se a regra contiver estrela kleene (por exemplo $(“+”F)^*$), também jogamos uma moeda e geramos zero ou uma repetição (claro que poderíamos escolher qualquer número inteiro aleatório $k\geq0$ e gerar $k$ repetições, mas para simplificar vamos nos concentrar na versão mais simples deste procedimento).Aqui está o que obtemos:

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

Uma invocação de generate_E() produz uma expressão aleatória.

O que poderia dar errado?Acontece que a execução deste procedimento na máquina real termina com estouro de pilha com bastante frequência.Claro, tecnicamente aqui temos a possibilidade de recursão infinita, mas minha intuição estava me dizendo que a probabilidade de atingir a profundidade da recursão $k$ decai exponencialmente com o aumento $k$, portanto, obter níveis profundos (digamos, 1000) é quase impossível.Aparentemente, algumas execuções consecutivas revelam que o procedimento pode facilmente atingir uma profundidade de muitos milhares (por profundidade quero dizer o número máximo de chamadas de procedimento que a pilha contém simultaneamente).

Estou curioso para saber como formalizar esse fato empírico.Eu quero uma fórmula para $P(profundidade = k)$, ou uma aproximação assintótica dele, ou uma desigualdade delimitando a cauda direita do CDF abaixo (algo como $P(profundidade > 1000) > 0,05$)

Minha tentativa

Tentei encontrar uma fórmula para $P(profundidade = k)$:

Vamos denotar $P(profundidade = k)$ como $P_E(k)$.Além disso, definimos valores semelhantes para gerar_F() e gerar_T() - $P_F(k)$ e $P_T(k)$ respectivamente.

Claramente (outro ramo de gerar_T), $$P_T(1) = \frac{1}{2}$$ e para $k > 1$ (então filial)$$P_T(k) = \frac{1}{2}P_E(k - 1)$$

A respeito de $P_F(k)$, podemos executar outro ramo, e dá prazo $$\frac{1}{2}P_T(k - 1)$$, ou então ramo, o que dá um pouco mais complicado $$ frac {1} {2} sum _ {(x, y) | max (x, y) = k - 1} {p_t (x) p_t (y)} $$ ou seja $$P_F(k)= \frac{1}{2}(P_F(k - 1) + \sum_{(x, y) | max(x, y) = k - 1}{P_T(x)P_T( e)})$$

Finalmente, a fórmula para $P_E(k)$ é quase o mesmo que para $P_F(f)$, só temos que substituir $P_T(x)$ com $P_F(x)$.

Agora podemos calcular alguns valores de $P_e(k)$

\begin{array} {|r|r|}\hline k & P_E(k) & P_E(k) ext{ em decimal}& P_E(k) ext{ por Monte-Carlo} \\ \hline 3 & \frac{33}{128} & \approx0,257812 & \approx0,2527 \\ \hline 6 & \frac{4448787585}{34359738368} & \approx0,129477 & \approx0,1282 \\ \hline 9 & \frac {14080391757747154038821618051813151497122305}{178405961588244985132285746181186892047843328} & \approx0,078923 & \approx0,0761 \\ \hline 12 & ext{ a fração é muito longa} & \approx0.053213 & \approx0.0530 \\ \hline \end{array}

Como podemos ver, as fórmulas recorrentes parecem ser verdadeiras, mas nenhuma delas me dá uma ideia do comportamento assintótico de $P_E(k)$, nem os primeiros valores dão uma pista sobre a fórmula na forma fechada.

Qualquer ajuda seria apreciada.

Answer 1

Seu processo é um exemplo clássico de um processo de ramificação.Começando com um $E$, temos uma expectativa $3/2$ muitos $F$é, $9/4$ muitos $T$s, e assim $9/8$ muitos restantes $E$está na expectativa.Desde $9/8 > 1$, não é surpreendente que seu processo muitas vezes não seja encerrado.

Para obter mais informações, precisamos saber a distribuição exata do número de $E$-descendentes, que é dado pela seguinte função geradora (veja o artigo da Wikipedia com link acima):$$ h (z) = frac {33} {128} + frac {7} {16} z + frac {15} {64} z^2 + frac {1} {16} z^3 + frac {1} {128} z^4.$$Isto implica que a probabilidade de extinção é $d \aproximadamente 0,717778143742483$ (resolvendo $h(z) = z$).Este é um limite superior para a probabilidade de seu procedimento terminar.

Podemos recuperar facilmente seus números considerando iterações de $h$.A probabilidade de o processo terminar em $ 3 mil $ passos é $h^{(k)}(0)$.Então computando $h(0),h(h(0))-h(0),h(h(h(0)))-h(h(0))$ e assim por diante, recuperamos os números da sua tabela.

Quando $k$ é grande, $h^{(k)}(0) \aproximadamente d$.Podemos calcular $h'(d) \aproximadamente 0,882115879977412$.Nós temos$$ frac {d - h^{(k)} (0)} {d - h^{(k -1)} (0)} = frac {h (d) - h (h^{(k -1)} (0))} {d -h^{(k -1)} (0)} aprox h '(d).$$Segue que$$ d - h^{(k)} (0) propto h '(d)^k.$$Portanto, a probabilidade de o processo terminar exatamente $ 3 mil $ passos é$$ 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, podemos verificar que a constante de proporcionalidade é aproximadamente $0.0248011196615094$.

Answer 2

Como Yuval observou, sabe-se que essa forma de gerar estruturas de dados recursivas aleatoriamente (geralmente) termina com um tamanho esperado infinito.

Existe, no entanto, uma solução para o problema, que permite pesar as escolhas recursivas de tal forma que o tamanho esperado esteja dentro de um certo intervalo finito: Amostradores Boltzmann.Eles são baseados na função geradora combinatória da estrutura e vêm da teoria combinatória das espécies.Para implementações práticas, você não precisa das partes teóricas.Uma boa introdução programática em Haskell pode ser encontrada no blog de Brent Yorgey.Se você consegue ler (ou decifrar) Haskell, portar a abordagem para sua própria estrutura de dados não é muito difícil.

Como exemplo de como uma derivação como a sua se parece dentro dessa estrutura, leia Contando e gerando termos no cálculo lambda binário por Grygiel & Lescanne (spoiler:é uma quantidade surpreendente de análise complexa).