Генерация случайных слов грамматикой

Question

Немного контекста

Я писал парсера для грамматики, а для целей тестирования я придумал идею создать некоторые случайные входы. Грамматика Я имела дело с гораздо сложнее, в этом вопросе я представил «минимальный рабочий пример» для простоты. И, конечно, я могу избежать проблемой, с которым я столкнулся, используя кучу тривиальной эвристики, но вопрос действительно заставляет меня удивляться.

проблема

Предположим, у нас есть типичная грамматика без контекста для арифметических выражений $ +, * $ , кронштейнов и целочисленных литералов:

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

Легко реализовать алгоритм Staighforward для генерации случайных слов этой грамматикой: мы реализуем отдельную процедуру для каждого нетерминального. Если нетерминал имеет несколько правил производства (как $ t $ делает), мы выбираем производственное правило, бросив монету. Если правило содержит звезду Kleene (например, $ ("+" f) ^ * $ ), мы также бросаем монету и сгенерируем ноль или одно повторение (уверены, что мы могли бы выбрать любой Случайное целое число $ k \ geq0 $ и генерировать $ K $ Repeties, но для простоты мы сосредоточимся на Простейшая версия этой процедуры). Вот что мы получаем:

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

.

Вызов generate_e () дает случайное выражение.

Что может пойти не так? Оказывается, что исполнение этой процедуры на реальной машине заканчивается с переполнением стека довольно часто. Конечно, технически здесь у нас есть возможность бесконечного рекурсии, но моя интуиция говорила мне, что вероятность достижения глубины рекурсии $ K $ Распадится экспоненциально с увеличением «Математический контейнер»> $ K $ , поэтому получение глубоких уровней (скажем, 1000) практически невозможно. По-видимому, несколько последовательных прогонов показывают, что процедура может легко достичь глубины многих тысяч (по глубине, которую я имею в виду максимальное количество процедурных вызовов в стеке содержит одновременно).

Я курио, как оформить этот эмпирический факт. Я хочу либо формулу для $ p (глубина= k) $ или асимптотическое приближение к нему или неравенство, ограниченное правым хвостом CDF ниже (что-то вроде $ P (глубина> 1000)> 0,05 $ )

Моя попытка

Я пытался придумать формулу для $ p (глубина= k) $ :

Давайте обозначаем $ p (глубина= k) $ как $ p_e (k) $ . Кроме того, мы определяем аналогичные значения для EM> Generate_f () () и generate_t () - $ p_f (k) $ и $ P_T (k) $ невысокий.

четко ( else ветвь generate_t ), $$ p_t (1)=frac {1} {2} $$ а для $ k> 1 $ ( затем филиал ) $$ P_t (k)=frac {1} {2} p_e (k - 1) $$

относительно $ p_f (k) $ , мы можем либо выполнять else , и это дает термин $$ \ frac {1} {2} p_t (k - 1) $$ , или Тогда филиал , что дает немного более сложной $$ \ 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)}) $$ .

Наконец, формула для $ p_e (k) $ почти такой же, как для $ p_f (f) $ , нам нужно только заменить $ P_T (x) $ с $ p_f (x) $ .

Теперь мы можем рассчитать некоторые значения $ p_e (k) $

\ begin {Array} {| r | r |} \ hline k & p_e (k) & p_e (k) \ text {в десятичных} & p_e (k) \ Text {Monte-Carlo} \\ \ hline 3 & \ FRAC {33} {128} & \ приблизительно 0.257812 & \ poont 0.2527 \\ \ hline 6 & \ FRAC {4448787585} {34359738368} & \ около 0.129477 & \ около 0.1282 \\ \ \ hline 9 & \ frac {1408039175774715418131514971813151497122305149712230514971223051224499615882449961843289204618432892046184328920461843328} & \ приблизительно 0.071 \\ \ hline 12 & \ Text {Фракция слишком длинная} & \ приблизительно \ около 0.0530 \\ \ hline \ end {массив}

Как мы видим, повторяющиеся формулы, кажется, являются правдой, но ни они не дают мне понимание асимптотического поведения $ P_E (K) $ , ни Первые значения дают подсказку на формуле в закрытой форме.

Любая помощь будет оценена.

Answer 1

Ваш процесс - это пример учебника Развлекательный процесс . Начиная с одного $ E $ , у нас есть ожидаемый $ 3/2 $ Многие $ f $ s, $ 9/4 $ Многие $ t $ s И поэтому $ 9/8 $ Многие остальные $ E $ S в ожидании. Поскольку $ 9/8> 1 $ , неудивительно, что ваш процесс часто не удается завершить.

Чтобы получить дополнительную информацию, нам нужно знать точное распределение количества $ e $ --offsprings, который дается следующей генерирующей функцией (см. Статья Википедии, связанная с вышеупомянутой): $$ h (z)=frac {33} {128} +} {7} + \ frac {7} {16} z + \ frac {15} {64} z ^ 2 + \ frac {1} {16} z ^ 3 + \ frac { 1} {128} z ^ 4. $$ Это подразумевает, что вероятность вымирания составляет $ d \ около 0.717778143742483 $ (путем решения $ h (z)= Z $ ). Это верхняя граница вероятности, что ваша процедура завершается.

Мы можем легко восстановить свои номера, учитывая итерации $ h $ . Вероятность того, что процесс завершается в 3K $ $ Этап, это $ h ^ {(k)} (0) $ . Таким образом, вычисление $ h (0), h (h (0)) - h (0), h (h (h (0))) - h (h (0)) $ И так далее, мы восстановим цифры в таблице.

Когда $ k $ большой, $ h ^ {(k)} (0) \ Прибл d $ < / span>. Мы можем вычислить $ h '(d) \ Приблизительно 0.882115879977412 $ . У нас есть $$ \ frac {d - h ^ {(k)} (0)} {d - h ^ {(k-1)} (0)}= \ frac {h (d) - h (h ^ {(k-1)} (0))} {d - h ^ {(k-1)} (0)} \ Прибл h '(d). $$ Следует, что $$ D - H ^ {(k)} (0) \ propto h '(d) ^ k. $$ Поэтому вероятность того, что процесс завершается в точности 3K $ $ $$ 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. $$ Эмпирически мы можем проверить, что константу пропорциональности составляет примерно $ 0.0248011196615094 $ .

Answer 2

Как отметил Ювал, этот способ случайно генерирующих рекурсивные структуры данных, как известно, (обычно) заканчивается бесконечным ожидаемым размером.

Есть, однако, есть решение проблемы, что позволяет взвесить рекурсивный выбор таким образом, что ожидаемый размер лежит в течение определенного конечного интервала: Bultzmann Samplers . Они основаны на комбинаторной зависимости от структуры и происходят из теории комбинаторных видов. Для практических реализаций вам не нужны теоретические детали. Хорошее программное введение в Haskell можно найти в блоге Brent yorgey . Если вы можете прочитать (или расшифровать) haskell, портировать подход к вашей собственной структуре данных не слишком сложно.

в качестве примера для того, как вывод, похожий на ваш вид в этой рамках, прочитайте Подсчет и генерация Условия в двоичном лямбде-исчислении Grygiel & Lescanne (спойлер: это удивительное количество сложного анализа).