logo

أتمتة الضغط لأسفل (PDA)

  • تُعد أتمتة الضغط لأسفل طريقة لتنفيذ CFG بنفس الطريقة التي نصمم بها DFA للقواعد النحوية العادية. يمكن لـ DFA أن يتذكر كمية محدودة من المعلومات، لكن يمكن أن يتذكر المساعد الرقمي الشخصي (PDA) كمية لا حصر لها من المعلومات.
  • إن أتمتة الضغط لأسفل هي ببساطة NFA معززة بـ 'ذاكرة مكدسة خارجية'. يتم استخدام إضافة المكدس لتوفير إمكانية إدارة ذاكرة 'آخر ما يدخل أولاً يخرج' لأتمتة الضغط لأسفل. يمكن لأتمتة الضغط لأسفل تخزين كمية غير محدودة من المعلومات على المكدس. يمكنه الوصول إلى كمية محدودة من المعلومات الموجودة على المكدس. يمكن لجهاز المساعد الرقمي الشخصي (PDA) دفع عنصر ما إلى أعلى المكدس وإزاحة العنصر من أعلى المكدس. لقراءة عنصر في المكدس، يجب أن تكون العناصر العلوية منبثقة وتضيع.
  • المساعد الرقمي الشخصي (PDA) أقوى من FA. أي لغة يمكن أن يقبلها الاتحاد الإنجليزي يمكن أن تكون مقبولة أيضًا بواسطة المساعد الرقمي الشخصي. يقبل المساعد الرقمي الشخصي (PDA) أيضًا فئة من اللغات لا يمكن حتى قبولها من قبل FA. وبالتالي فإن المساعد الرقمي الشخصي (PDA) أفضل بكثير من FA.
أتمتة الضغط لأسفل

مكونات المساعد الرقمي الشخصي:

شريط الإدخال: يتم تقسيم شريط الإدخال إلى عدة خلايا أو رموز. رأس الإدخال للقراءة فقط ويمكن أن يتحرك فقط من اليسار إلى اليمين، رمزًا واحدًا في كل مرة.

السيطرة المحدودة: يحتوي عنصر التحكم المحدود على بعض المؤشرات التي تشير إلى الرمز الحالي الذي سيتم قراءته.

كومة: المكدس عبارة عن هيكل يمكننا من خلاله دفع العناصر وإزالتها من طرف واحد فقط. لها حجم لانهائي. في المساعد الرقمي الشخصي، يتم استخدام المكدس لتخزين العناصر مؤقتًا.

التعريف الرسمي للمساعد الرقمي الشخصي:

يمكن تعريف المساعد الرقمي الشخصي (PDA) على أنه مجموعة من 7 مكونات:

س: المجموعة المحدودة من الحالات

∑: مجموعة الإدخال

ج: رمز المكدس الذي يمكن دفعه وإخراجه من المكدس

س0: الحالة الأولية

شريط أدوات الوصول السريع لـ MS Word

مع: رمز البداية الموجود في Γ.

F: مجموعة من الحالات النهائية

د: وظيفة رسم الخرائط التي تستخدم للانتقال من الحالة الحالية إلى الحالة التالية.

الوصف الفوري (المعرف)

المعرف هو تدوين غير رسمي لكيفية قيام المساعد الرقمي الشخصي بحساب سلسلة الإدخال واتخاذ القرار بقبول السلسلة أو رفضها.

الوصف اللحظي هو ثلاثي (q, w, α) حيث:

س يصف الوضع الحالي.

في يصف المدخلات المتبقية.

ما هو التصدير في لينكس

أ يصف محتويات المكدس، أعلى اليسار.

تدوين الباب الدوار:

⊢ العلامة تصف علامة الباب الدوار وتمثل حركة واحدة.

⊢* العلامة تصف سلسلة من التحركات.

على سبيل المثال،

(ص، ب، تي) ⊢ (ف، ث، α)

في المثال أعلاه، أثناء الانتقال من الحالة p إلى q، يتم استهلاك رمز الإدخال 'b'، ويتم تمثيل الجزء العلوي من المكدس 'T' بسلسلة جديدة α.

مثال 1:

تصميم المساعد الرقمي الشخصي لقبول اللغة أنب2n.

حل: في هذه اللغة، عدد n من a ينبغي أن يتبعه عدد 2n من b's. ومن ثم، فإننا سوف نطبق منطقًا بسيطًا للغاية، وهو أنه إذا قرأنا حرف 'a' واحدًا، فسندفع حرفين إلى المكدس. بمجرد أن نقرأ 'b'، فمن أجل كل حرف 'b' يجب أن يتم إخراج حرف 'a' واحد فقط من المكدس.

يمكن بناء المعرف على النحو التالي:

 δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) 

الآن عندما نقرأ b، سنقوم بتغيير الحالة من q0 إلى q1 ونبدأ في ظهور 'a' المقابل. لذلك،

 δ(q0, b, a) = (q1, ε) 

وبالتالي سيتم تكرار عملية ظهور 'b' ما لم تتم قراءة جميع الرموز. لاحظ أن الإجراء المنبثق يحدث في الحالة q1 فقط.

قوة ذاكرة التخزين المؤقت النظيفة npm
 δ(q1, b, a) = (q1, ε) 

بعد قراءة كل الحروف b، يجب أن تظهر كل الحروف المقابلة لها. ومن ثم عندما نقرأ ε كرمز إدخال، فلا ينبغي أن يكون هناك أي شيء في المكدس. وبالتالي فإن التحرك سيكون:

 δ(q1, ε, Z) = (q2, ε) 

أين

المساعد الشخصي الرقمي = ({q0، q1، q2}، {a، b}، {a، Z}، δ، q0، Z، {q2})

يمكننا تلخيص المعرف على النحو التالي:

 δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) δ(q0, b, a) = (q1, ε) δ(q1, b, a) = (q1, ε) δ(q1, ε, Z) = (q2, ε) 

سنقوم الآن بمحاكاة المساعد الرقمي الشخصي (PDA) هذا لسلسلة الإدخال 'aaabbbbbbb'.

حلقة foreach
 δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ) ⊢ δ(q0, abbbbbb, aaaaZ) ⊢ δ(q0, bbbbbb, aaaaaaZ) ⊢ δ(q1, bbbbb, aaaaaZ) ⊢ δ(q1, bbbb, aaaaZ) ⊢ δ(q1, bbb, aaaZ) ⊢ δ(q1, bb, aaZ) ⊢ δ(q1, b, aZ) ⊢ δ(q1, ε, Z) ⊢ δ(q2, ε) ACCEPT 

مثال 2:

تصميم المساعد الرقمي الشخصي لقبول اللغة 0ن1م0ن.

حل: في هذا المساعد الرقمي الشخصي، عدد n من الأصفار متبوع بأي عدد من 1 متبوعًا بعدد n من 0. ومن ثم فإن منطق تصميم مثل هذا المساعد الرقمي الشخصي سيكون كما يلي:

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

على سبيل المثال:

أتمتة الضغط لأسفل

يمكن كتابة هذا السيناريو في نموذج المعرف على النحو التالي:

 δ(q0, 0, Z) = δ(q0, 0Z) δ(q0, 0, 0) = δ(q0, 00) δ(q0, 1, 0) = δ(q1, 0) δ(q0, 1, 0) = δ(q1, 0) δ(q1, 0, 0) = δ(q1, ε) δ(q0, ε, Z) = δ(q2, Z) (ACCEPT state) 

سنقوم الآن بمحاكاة المساعد الرقمي الشخصي (PDA) هذا لسلسلة الإدخال '0011100'.

 δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z) ⊢ δ(q0, 11100, 00Z) ⊢ δ(q0, 1100, 00Z) ⊢ δ(q1, 100, 00Z) ⊢ δ(q1, 00, 00Z) ⊢ δ(q1, 0, 0Z) ⊢ δ(q1, ε, Z) ⊢ δ(q2, Z) ACCEPT