文法によるランダムな単語の生成
https://cs.stackexchange.com/questions/121884
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
ビットのコンテキスト
私は文法のためのパーサを書いていて、テスト目的のために私はいくつかのランダムな入力を生成するという考えを思いついています。この質問では、私が簡単にするために「最小限の実施例」を提示した文法ははるかに複雑でした。そしてもちろん、私は私がたくさんの自由なヒューリスティックを使って直面した問題を避けることができますが、この問題は本当に私を不思議にします。
問題
$ +、* $ 、括弧、整数リテラルの算術式のための典型的なコンテキストの文法があるとします。
$$ e \ longrehregrew f（ "+" f）^ * $$ $$ F \ LongRitherArrow T（ "*" t）^ * $$ $$ T \ LongreRitherRow int | "（" E "）" $$
この文法によってランダムな単語を生成するためのStaighForwardアルゴリズムを実装するのは簡単です。私たちは、各非介護者に対して別の手順を実装します。非終端で複数の製造規則がある場合（ $ t $ のように）、コインを投げて生産規則を選択します。ルールにKleene Starが含まれている場合（例： $（ "+" f）^ * $ ）、私たちはまたコインを投げ、ゼロまたは1回の繰り返しを生成しますRandom Integer $ k \ geq00 $ と生成 $ k $ 繰り返しは、この手順の最も簡単なバージョン）。これが私たちが得るものです：
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）はほとんど不可能です。明らかに、いくつかの連続した実行は、手続きが数千の深さを簡単に到達させることができることを明らかにしています（深さIを意味すると、スタックに同時に含まれる最大数のプロシージャー数が同時に含む）。
私はこの経験的事実を形式化する方法をクリアです。 $ p（depth= k）$ の式、またはそれの漸近近似、または下のCDFの不等式境界右テール（<スパンのようなもの） class="math-container"> $ p（深さ> 1000）> 0.05 $ ）
私の試み
$ pの式を思い付くことが試みました（depth= k）$ ：
$ p（depth= k）$ を $ p_e（k）$ として表しましょう。また、 generate_f（）および generate_t（） - $ p_f（k）$ の類似値を定義します。 $ p_t（k）$ は、上で
明らかに（ else_t の 分岐）、 $$ p_t（1）=frac {1} {2} $$ と $ k> 1 $ （ branch） $$ 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 | R | r | r | \ hline k＆p_e（k）＆p_e（k）\ text {10進}＆p_e（k）\テキスト{by Monte-Carlo} \ \ hline 3＆\ frac {33} {128}＆\約0.257812＆\約0.257812 \ \ hline 6＆\ frac {4448787585} {34359738368}＆\ 200.129477 ＆\ approx0.1282 \\ \ HLINE 9＆\ FRAC {14080391757747154038821618051813151497122305} {178405961588244985132285746181186892047843328}＆\ approx0.078923＆\ approx0.0761 \\ \ HLINE 12＆\テキスト{画分が長すぎる}＆\ approx0.053213＆ \約0.0530 \ hline \ end {array}
私たちが見ることができるように、再発式は当てはまるようですが、 $ p_e（k）$ の漸近的な動作に関する洞察を教えていません。最初の値は閉じた形で式に手がかりを与えます。
任意の助けが理解されるでしょう。
解決
あなたのプロセスは分岐プロセスの教科書例です。 1つの $ e $ から始めて、 $ 3/2 $ $ f $ s、 $ 9/4 $ 多くの $ t $ s SO $ 9/8 $ 多くの残りの $ E $ sは予想されます。 1 $ 以来、あなたのプロセスが終了に失敗しなかったことは驚くべきことではありません。
より多くの情報を得るためには、以下の生成機能によって与えられた $ e $ -OFFSPRINGSの正確な分布を知る必要があります。上記にリンクされたウィキペディアの記事）： $$ h（z）=frac {33} {128} + \ 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 $ < /スパン>。 $ 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 $ です。
他のヒント
YUVALが注目されているため、再帰的データ構造をランダムに生成するこの方法は、無限の予想サイズで（通常）保持されていることがわかっています。
問題の解決策は、予想されるサイズが特定の有限の間隔内にあるように再帰的な選択を重量にすることを可能にします。
あなたの様子のような派生がそのフレームワークの中でどのように見えるかの例として、を読んでください。 Grygiel＆LeScanne（スポイラー：それは驚くほど複雑な分析の量です）によるバイナリλcalulusの用語
