توليد كلمات عشوائية من قبل القواعد

Question

قليلا من السياق

كنت أكتب محللا لقواعد النحو، وللموقع لأغراض الاختبار، فقد وصلت إلى فكرة لتوليد بعض المدخلات العشوائية. كان القواعد القواعد التي كنت أتعامل معها أكثر تعقيدا، في هذا السؤال قدمت "الحد الأدنى من مثال العمل" للبساطة. وبالطبع، أنا قادر على تجنب القضية التي واجهتها باستخدام مجموعة من الاستدلال تافهة، ولكن السؤال حقا يجعلني أتساءل.

المشكلة

لنفترض أن لدينا قواعد نجمية خالية من السياق للتعبير الحسابي عن $ +، * $ ، الأقواس، الحرفي الصحيحة:

$$ E \ LongRightarrow F ("+" F) ^ * $$ $$ f \ longreightarrow t ("*" t) ^ * $$ $$ T \ LongRightarrow int | "(" E ")" $

من السهل تنفيذ خوارزمية Staighforward لتوليد كلمات عشوائية من خلال هذا القواعد: نحن ننفذ إجراء منفصل لكل unternerminal. إذا كان لدى NoTerminal قواعد إنتاج متعددة (ك $ T $ هل)، نختار قاعدة الإنتاج عن طريق قذف عملة معدنية. إذا كانت القاعدة تحتوي على نجمة Kleene (على سبيل المثال $ ("+" f) ^ * $ )، ونحن نرز أيضا عملة معدنية وتولد صفر أو تكرار واحد (بالتأكيد يمكننا اختيار أي عدد صحيح عشوائي $ k \ geq0 $ وتوليد $ K $ retitions، ولكن للبساطة سنركز على أبسط نسخة من هذا الإجراء). هنا هو ما نحصل عليه:

giveacodicetagpre.

استدعاء من Generate_e () يعطي تعبيرا عشوائيا.

ماذا يمكن أن يحدث خطأ؟ اتضح أن تنفيذ هذا الإجراء على الجهاز الحقيقي ينتهي بضغط مكدس في كثير من الأحيان. بالطبع، من الناحية الفنية هنا لدينا إمكانية للحصول على العودية التي لا نهاية لها، لكن حدس بلدي كان يقول لي أن احتمال الوصول إلى عمق العودية $ K $ يتحلل بشكل كبير مع زيادة $ K $ ، وبالتالي الحصول على مستويات عميقة (دعنا نقول، 1000) مستحيل تقريبا. على ما يبدو، يكشف عدد قليل من أشواط متتالية أن الإجراء يمكن أن يصل بسهولة إلى عمق العديد من الآلاف (عن طريق عمق يعني أقصى عدد من الإجراءات المكالمات تحتوي على المكدس في وقت واحد).

أنا ducios كيفية إضفاء الطابع الرسمي على هذه الحقيقة التجريبية. أريد إما صيغة $ p (العمق= k) $ ، أو تقريب مقارب منه، أو عدم المساواة يحطيل الذيل الصحيح من CDF أدناه (شيء مثل $ p (عمق> 1000)> 0.05 $ )

محاولتي

حاولت التوصل إلى صيغة $ p (عمق= k) $ :

دعنا ندرس $ p (عمق= k) $ ك $ p_e (k) $ . أيضا، نحدد قيم مماثلة ل gendate_f () و gendate_t () - $ p_f (k) $ و $ p_t (k) $ professivestely.

بوضوح ( فرع endate_t )، $$ p_t (1)=frac {1} {2} $$ ول $ k> 1 $ ( ثم الفرع) $$ p_t (k)=frac {1} {2} p_e (k - 1) $

فيما يتعلق $ p_f (k) $ ، يمكننا إما تنفيذ آخر ، وهذا يمنح المصطلح $$ \ FRAC {1} {1} 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) $

\ ابدأ {array} {| r | r |} \ hlline k & p_e (k) & p_e (k) \ text {in decimal} & p_e (k) \ نص {by monte-carlo} \\ \ hlline 3 & \ frac {33} {128} {} {128}} {} {128}} {}} و\ approx0.1282 \\ \ hline 9 و \ فارك {14080391757747154038821618051813151497122305} {} 178405961588244985132285746181186892047843328 و\ approx0.078923 و\ approx0.0761 \\ \ hline 12 و\ النص {جزء طويل جدا} و\ approx0.053213 & \ حوالي 0.0530 \\ \ hline \ end {array}

كما نرى، يبدو أن الصيغ المتكررة تبدو صحيحة، ولكنها لا تعطيني نظرة ثاقبة حول السلوك غير المتفظال ل $ p_e (k) $ ، ولا القيم الأولى تعطي فكرة عن الصيغة في شكل مغلق.

سيكون موضع تقدير أي مساعدة.

Answer 1

العملية الخاصة بك هو مثال كتابي على عملية المتفرعة . بدءا من $ e $ ، لدينا 3/2 $ $ العديد من $ f $ s، 9/4 $ $ العديد من $ T $ s ، وهكذا $ 9/8 $ العديد من $ E $ s في توقع. منذ 9/8 دولار> 1 دولار ، ليس من المستغرب أن تكون عمليةك في كثير من الأحيان فشلت في إنهاء.

للحصول على مزيد من المعلومات، نحتاج إلى معرفة التوزيع الدقيق لعدد $ E $ -pophoversprings، والتي يتم تقديمها بواسطة الوظيفة التوليدية التالية (انظر مقالة ويكيبيديا مرتبطة أعلاه): $$ H (z)=frac {} {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 (h (0))) - h (h (0)) $ وهلم جرا، نستعيد الأرقام في طاولتك.

عندما $ K $ كبير، $ h ^ {(k)} (0) \ impally 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-h ^} (0)} \ impally \ h '(d). $ إنه يتبع هذا $$ D - H ^ {(k)} (0) \ propto h '(d) ^ k. $ لذلك احتمال أن تنتهي العملية بالضبط $ 3K $ الخطوات هي $$ ح ^ {(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

كما لاحظ يوفال، من المعروف أن طريقة توليد هياكل البيانات العودية التي تنتج بشكل عشوائي (عادة) بحجم متوقع لانهائي.

هناك حل للمشكلة، يتيح للمرء أن يزن الخيارات العودية بطريقة توقع حجمها في غضون فترة فاصلة محدودة: boltzmann samplers . وهي تستند إلى وظيفة توليد الحركة الهيكلية للهيكل وتأتي من نظرية الأنواع المختلستية. للتطبيقات العملية، لا تحتاج إلى الأجزاء النظرية، رغم ذلك. يمكن العثور على مقدمة برنامجية جيدة في Haskell في مدونة برنت يورغبى . إذا كان بإمكانك قراءة (أو فك شفرة) Haskell، فإن Porting نهج بنية البيانات الخاصة بك غير صعبة للغاية.

كمثال لكيفية البحث عن الاشتقاق لك في هذا الإطار، اقرأ حساب وتوليد المصطلحات في حساب التفاضل والتكامل ثنائي لامدا (/a> بواسطة جريغيل & Lescanne (المفسد: إنه مبلغ مفاجئ من التحليل المعقد).