تحويل المساعد الرقمي الشخصي إلى CFG

Question

أحاول أن أفهم هذا المثال لتحويل المساعد الرقمي الشخصي إلى CFG ولكني لا أفهم الفكرة بشكل صحيح تمامًا.لدي الفهم العام للنظرية أنه إذا $p,q\ \epsilon\ Q $ و $X \فاريبسيلون\ \جاما$ ل $[بإكسك]$ لقد قمنا بتضمين تسلسل الاشتقاقات التي من شأنها أن تظهر Xمن المكدس.

أفهم جزئيًا ما يحدث ولكن لا يبدو أنني أفهم كيف يمكنني فتح المنتجات لتشكيل سلاسل حتى أتمكن من فهمها بوضوح.خذ الإنتاج (5) في المثال على سبيل المثال.مما أفهمه أننا في الحالة p نريد أن ننبثق A وفي النهاية يجب أن نكون في الحالة p مع مكدس فارغ.كما نقرأ 0 لدينا صفر في الإنتاج تليها $[pAq][qAp]$, هذا هو الشيء الذي لا أفهمه لأنه إذا نظرنا إلى المساعد الرقمي الشخصي (PDA) فلا توجد طريقة للذهاب إليه س على القراءة 0.أود أن أعرف ما الذي يحدث حقًا.

تمت الإجابة على سؤال ذي صلة هنالكن لا أستطيع أن أفهم كيفية إزالة حيرتي.

Answer 1

لديك الحدس الأساسي الصحيح.المتغير $[ع،أ،ف]$ يمثل مجموعة (السلاسل المقبولة) من الحسابات من الحالة $p$ للدولة $س$ من شأنها أن تظهر الرمز العلوي $أ$ من المكدس.

من الناحية الفنية العلاقة بين القواعد $ج$ والمساعد الشخصي الرقمي $م$ موجود في الجزء العلوي من الشريحة التي تعرضها.

ثم يتبع البناء العودية.إذا انبثق المساعد الشخصي الرقمي $أ$ ولكن يدفع $B_1B_2B3$ سوف تحل القواعد محل الحساب $أ$ يبدأ في $p$ وتنتهي في $س$ إلى ثلاث حسابات منفصلة $[q_1,B_1,q_2][q_2,B_1,q_3][q_3,B_1,q]$.هنا الدول المتوسطة $q_2,q_3$ غير معروفة وهي خمنت بواسطة القواعد.فقط $q_1$ معروفة، لأنها الحالة التي تنتقل إليها تعليمات المساعد الرقمي الشخصي.

ملاحظتك في محلهاقد يقدم هذا البناء القياسي ثلاثة توائم $[ع،أ،ف]$ سيكون ذلك عديم الفائدة.في المثال الخاص بك لن يكون هناك أي حسابات من $س$ ل $p$ حتى ثلاثة توائم $[س،أ،ص]$ لا يتم استخدامه أبدًا في الاشتقاق الناجح.هذا ليس إشكاليا.البناء ينتج فقط كل الاحتمالات، والمتغيرات التي يتبين أنها غير مجدية يمكن إزالتها بعد ذلك إذا أراد المرء ذلك حقًا.

ملحوظة. السؤال الآخر الذي ترتبط به يستخدم نموذجًا آليًا مختلفًا لأسلوب Sipser!يتم دفع رموز المكدس واحدًا تلو الآخر دون ظهورها في نفس الوقت.ولزيادة الارتباك إجابة الموضح في هذا السؤال يتطابق تمامًا مع البناء من شريحتك!