الطول الإجمالي للإدخال إلى أتمتة الضغط لأسفل والذي يقبل بواسطة مكدس فارغ هو الحد الأعلى لحالات الأرقام ورموز المكدس

Question

كنت أتصفح النص الكلاسيكي "مقدمة في نظرية الأتمتة واللغات والحساب" (الإصدار الثالث) بقلم جيفري أولمان وجون هوبكروفت وراجيف موتواني, ، حيث صادفت بعض العبارات حول أتمتة الضغط لأسفل (PDA) والتي تقبل بواسطة مكدس فارغ، على النحو التالي:

1. $ن$, ، الطول الإجمالي للإدخال، هو بالتأكيد حد أعلى لعدد الحالات ورموز المكدس.

2.يمكن لقاعدة واحدة وضع رموز n تقريبًا على المكدس.

تم الإدلاء بالعبارات التالية بينما كان المؤلفون على وشك تقديم بعض الملاحظات حول خصائص قرار المصابيح الفلورية المتضامة (اللغات الحرة السياق)

والآن، إليك بعض النقاط التي ربما أستطيع من خلالها مناقضة هذا الادعاء بدلاً من إثبات صحته.

1. يفترض $ن$, ، هو الطول الإجمالي للإدخال، ولكن وفقًا لتصميم المساعد الرقمي الشخصي، قد يحدث أنه لقبول سلسلة الإدخال، لا تكون جميع حالات المساعد الرقمي الشخصي متضمنة، لذلك لا يمكننا أن نقول ذلك $ن$ هو الحد الأعلى لعدد الحالات الموجودة في المساعد الرقمي الشخصي.

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

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

لقد أرفقت الجزء المقابل من النص أدناه:

Answer 1

هذا القسم لا يتحدث عن التحليل.الخوارزميات المشار إليها هي خوارزميات للتحويل بين CFGs وأجهزة المساعد الرقمي الشخصي من أنواع مختلفة.السؤال هو، كالعادة، "ما هو التعقيد الحسابي للخوارزمية"، ويتم التعبير عن الإجابة، كالعادة، من حيث حجم المدخلات -- إلى الخوارزمية.

إن المدخلات إلى الخوارزمية التي تحول المساعد الرقمي الشخصي إلى CFG هي المساعد الرقمي الشخصي، وحجم المدخلات - المقياس المتري لتعقيد الخوارزمية - هو حجم المساعد الرقمي الشخصي *".وهذا ما ينوي المؤلفون ن يكون.

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

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