اوتومات الدفع السفلي

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في علم الحاسوب , الأوتومات الدفع السفلي او بإختصار "PDA" هو نموذج حاسوبي بسيط يقوم على فكرة بنية البيانات المكدس (stack) , حيث انه يستخدمه بأنه ذاكرة اضافية يُخزن فيها النتائج غير نهائية ليُعيد استخدامها لاحقا ضمن العمليات المُتاحة لهذا النموذج . هنالك نوعان من اوتوماتات الدفع السفلي : اوتومات الدفع السفلي القطعي (DPA) , اوتومات الدفع السفلي غير القطعي (PDA) . على خلاف النماذج الابسط اوتومات الدفع السفلي غير القطعي "اقوى" من قرينه القطعي , اي يوجد لغات التي يمكن تقريرها بواسطة PDA ولكن ليس بواسطة DPA . اوتومات الدفع السفلي عمليا هو اوتومات حالات محدودة مُزود بمكدس LIFO اي من يدخل اخرا يخرج اولا , أول من أنتج الPDA's هو Anthony Oettinger في عام 1963 وقد كان المُكَّدس مستخدماً منذ زمن طويل ، إلا أن أبحاثه نَظَّمت دمجه في أوتومات منتهي .ولعل أحد أهم المبرهنات في هذا المجال هي : لكل PDA يمكن بناء قواعد حرة السياق تنتج نفس اللغة . اهمية هذا الاوتومات تتبين من حقيقة انه يُستخدم كثيرا في عملية التجزئة (parsing) وخاصة انه أسهل للبرمجة من القواعد حرة السياق وقد تبين انهما ذوي قوة مضارعة .

تعريف[عدل]

اوتومات الدفع السفلي هو السباعية :  \mathcal{A}=(Q,\Delta,\Gamma,\delta,q_{in},A_{in},F) حيث يتحقق :

Pushdown-overview.svg
  1. Q هي مجموعة منتهية من الحالات .
  2. \Delta هي ابجدية المُدخل (اي من اية حروف يمكن ان تتركب سلسلة المُدخل)
  3. \Gamma هي ابجدية المُكدس (يجب ان تحوي حروفا غير تلك التي نستخدمها للمُدخل )
  4.  \delta \subseteq Q\times (\Delta \cup \{\lambda\} )\times \Gamma \times Q \times \Gamma^* اي انها مجموعة جزئية منتهية ل- Q\times (\Delta \cup \{\lambda\} )\times \Gamma \times Q \times \Gamma^* , وتُسمى علاقة الانتقال (transition relation). وكل  (p,a,A,q,\alpha)\in \delta تُسمى أمر (او نقلة) وهو يصف الانتقال من الحالة  p للحالة q في حين أنَّ a هو الحرف التالي من المُدخل و-  A هو الرمز الواقع في اعلى المُكدس . والتغيير يتحقق بقراءة الحرف a واخراج  A من المُكدس واحلال  \alpha مكانه في المُكدس .
  5. الحالة الابتدائية  q_{in}\in Q
  6. رمز المُكدس الابتدائي  A_{in}\in \Gamma
  7.  F\subseteq Q مجموعة الحالات النهائية .

ملاحظات :

  1. يمكن اعتبار  \delta دالة من المجموعة Q\times (\Delta \cup \{\lambda\} )\times \Gamma لمجموعة جزئية ل- Q \times \Gamma^* حينها يمكننا ان نكتب :  (q,\alpha)\in \delta(p,a,A) .
  2. نرمز ب-  \Gamma^* مجموعة كل السلاسل (او الكلمات) التي تتركب من المجموعة  \Gamma وكذا الامر ل- \Delta^* .

صورة فورية[عدل]

صورة فورية(configuration) لاوتومات الدفع السفلي  \mathcal{A} مُكونة من حروف المُدخل التي لم يتم قراءتها بعد والحالة الحالية والمحتوى الحالي للمُكَّدس اي انه مجموعة الصور الفورية هي مجموعة جزئية ل-\Delta^* \times Q \times \Gamma .

علاقة الخطوة[عدل]

دالة الانتقال  \delta يمكننا بواسطتها تعريف علاقة الخطوة , \vdash_{\mathcal{A}} , والعلاقة مُعرفة على مجموعة الصور الفورية :

 (ax,p,A\gamma) \vdash_{\mathcal{A}} (x,q,\alpha\gamma) \iff (p,a,A,q,\alpha)\in \delta ,x\in \Delta^* , \gamma\in\Gamma^*

من تبعيات هذا التعريف انَّ الاوتومات لا يمكنه المتابعة اذا ما فرغ المُكَدس لانه بكل خطوة عليه اخراج حرف او رمز من المكدس .

حساب[عدل]

حساب اوتومات ذو مكدس هو متتالية خطوات متلاحقة , وعلاقة الحساب هي المنغلق الانعكاسي والمتعدي ,\vdash^*_{\mathcal{A}}, لعلاقة الخطوة .

لغة الاوتومات[عدل]

PDA يقبل المدخل اذا حسابه على المُدخل بداية من الحالة الابتدائية مع وجود رمز المُكدس الابتدائي وتمام قراءة المُدخل واحد الامرين التاليين يتحقق :

  1. ينتهي الامر بحالةٍ نهائية .
  2. او ينتهي الامر بمُكدس فارغ .

بشكل عام هاتان اللغتان , لاوتومات مُعين , ليستا بالضرورة متساويان . لاحظ انه في الحالة الثانية لا يهم أية حالة وقفنا عليها (سواءا كانت نهائية او لا ) .

بناءا على ما تقدم سالفا نُعرف اللغتين بالشكل التالي :

فليكن  \mathcal{A} اوتومات دفع سفلي , نعرف اللغتين التاليتين :

  1. لغة الحالة النهائية للاوتومات  \mathcal{A} هي :  L(\mathcal{A})=\{x\in\Delta^*| (x,q_{in},A_{in}) \vdash^*_{\mathcal{A}} (\lambda,q,\gamma) \ \mbox{for some} \ q\in F ,\gamma\in \Gamma^* \}
  2. لغة المُكدس الفارغ للاتومات  \mathcal{A} هي :  N(\mathcal{A})=\{x\in\Delta^*| (x,q_{in},A_{in}) \vdash^*_{\mathcal{A}} (\lambda,q,\lambda) \ \mbox{for some} \ q\in Q \}

بشكل عام لا يتحقق التساوي بين اللغتين لكل اوتومات , ولكن يمكن بناء اوتومات اخر بحيث يتحقق التساوي , اي انه يتحقق التالي :

فليكن \mathcal{A} اوتومات دفع سفلي حينها يمكننا بناء اوتومات \mathcal{A}' بحيث يتحقق :  N(\mathcal{A})=L(\mathcal{A}') . وكذا العكس .

لغات حرة السياق[عدل]

كل قواعد حر السياق الذي ينتج لغة يمكن تحويله بسهولة إلى اوتومات دفع سفلي يتعرف (recognize) على اللغة عينها . فليكن  G=(N,T,S,P) نعرف الاوتومات التالي ذي الحالة الواحدة : \mathcal{A}=({q},T,N\cup T ,\delta , q,S,\emptyset) بحيث أنَّ \delta قوانينها كالتالي :

  •  (q,\lambda,A,q,\alpha) لكل  A\to \alpha\in P . "توسيع"
  •  (q,a,a,q,\lambda) لكل  a\in T . "تطابق"

حسابات  \mathcal{A} تقابل الاشتقاقات الاكثر يسارا (leftmost derivations) \Rightarrow^* _{G,l} ل- G , رسميا : فليكن  x\in T^* وليكن \alpha\in (N\cup T)^* اذا  (x,q,S)\vdash^*_\mathcal{A}(\lambda,q,\alpha) حينها يتحقق : S\Rightarrow^*_{G,l}x\alpha . كما ان العكس يتحقق لكل  \alpha \in N (N\cup T)^* \cup  \{ \lambda\} .

حينما نأخذ  \alpha=\lambda نجد أن :  S\Rightarrow^* _{G,l} x فقط اذا  (x,q,S) \vdash^*_\mathcal{A} (\lambda,q,\lambda لكل  x\in T^* , وهذا يعني أنَّ  L(G)=N(\mathcal{A}) , هذا التوافق يُظهر أنَّ الاوتومات ذي الحالة الواحدة (حين الاخذ بالاعتبار لغة المُكدس الفارغ كما سبق تعريفها) مكافئ للقواعد حرة السياق . التكافؤ لا يقف عند هذا الحد إذ أنَّ التكافؤ الكامل بين اوتومات الدفع السفلي وبين القواعد حرة السياق هو تكافؤ شامل وهذه النتيجة توصل اليها كل من نعوم تشومسكي و مارسيل-بوول شوتزنبرجر , وإيفي . والمبرهنة تنص على أن كل لغة تُقبل بواسطة اتومات دفع سفلي سواءا اكان ذلك بفراغ المُكدس ام بالوصول إلى حالة نهائية من مجموعة الحالات النهائية , فقط اذا كانت هذه اللغة هي لغة حرة السياق .

صفات انغلاق[عدل]

فلتكن A , B لغتين اللتين تُمَيَّزَان (recognized) بواسطة اوتماتي الدفع السفلي  M_A,M_B على التوالي .

1. الاتحاد : اللغة A\cup B يمكن أن تُمَيَّز بواسطة اوتومات دفع سفلي  M_{A\cup B} . بحيث أن  M_{A\cup B} مركب من الاوتوماتين  M_A,M_B مع اضافة حالة جديدة وفي دالة العبور نضيف لهذه الحالة عبور بواسطة \lambda , كما هو مبين في الصورة .

PDA close under union.png

2. التسلسل : اللغة  A\circ B يمكن أن تُمَيَّز بواسطة اوتومات دفع سفلي  M_{A\circ B} . بحيث أن  M_{A\circ B} مركب من الاوتوماتين  M_A,M_B , وفي دالة العبور نضيف عبور بواسطة \lambda من مجموعة الحالات النهائية التي في A لبداية B .

3. فلتكن R لغة منظمة(regular language) حينها اللغة  A\cap R يمكن تميزها بواسطة اوتومات دفع سفلي .

4. نجمة كليين : اللغة A^* يمكن أن تُمَيَّز بواسطة اوتومات دفع سفلي  M_{A^*} . هذا يُبرهن بواسطة القواعد حرة السياق .

5. مورفزم عكسي : فليكن  h:\Sigma \to \Delta^* مورفزم حينها اللغة :  h^{-1}(A) \subseteq \Sigma^* يمكن أيضا ان تُميز بواسطة اوتومات دفع سفلي .

اوتومات دفع سفلي قطعي[عدل]

من وجهة نظر عملية اوتومات الدفع السفلي بصورته هذه لا يُعتبر مفيدا لتمييز اللغات او حتى للتحليل النحوي (parsing) , وذلك لانه ليس قطعيا اي انه في كل خطوة عليه ان يتحزر الصواب ويسلك طريقه . وخلافا لاتومات الحالات المنتهية فان اوتومات الدفع السفلي القطعي لا ينتج كل لغة حرة السياق اي انه ليس موديل لهذه اللغات كما هو الحال مع القواعد حرة السياق وكذا اوتومات الدفع السفلي غير القطعي .

تعريف[عدل]

اوتومات الدفع السفلي  \mathcal{A} =(Q,\Delta,\Gamma,\delta,q_{in} ,A_{in},F) قطعي اذا تحقق التالي :

  • لكل  p\in Q , كل  a\in \Delta وايضا كل  A\in \Gamma , \delta لا تحوي التعليم (instruction)  (p,\lambda,A,q,\alpha) وكذلك التعليم  (p,a,A,q',\alpha')
  • لكل  p\in Q ,ولكل  a\in \Delta\cup \{\lambda\} ولكل  A\in \Gamma يوجد في  \delta على الاكثر تعليم واحد  (p,a,A,q,\alpha) .

ملاحظة :

  • لاحظ انه مسموح تواجد التعليمين  (p,\lambda,A,q,\alpha)\ , \ (p,a,A',q',\alpha') في  \delta في حين أن  a\ne \lambda وكذلك  A\ne A' اي أن الاختيار يكون حسب رأس المكدس العلوي وخلاف هذا الصورتين الفوريتين متساويتين .

لغات الاوتومات القطعي[عدل]

كما هو الحال مع الاوتومات الدفع السفلي الغير قطعي عندنا طريقتين لتعريف لغة الاوتومات : اما عن طريق الوصول إلى حالة نهائية مع انتهاء المُدخل او بفراغ المُكدس مع انتهاء المُدخل . اما اللغات من الطريقة الثانية فهي لغات حرة البدايات (prefix free) اي : انَّ هذه اللغات لا تحوي الكلمة او ايا من بدايتها في نفس الوقت . ولهذا السبب فإن هذه العائلة لا يمكن مقارنتها بعائلة اللغات المنتظمة (regular) .

وكما كان الحال مع اللغات حرة السياق وعلاقتها بأوتومات الدفع السفلي يمكن أيضا هنا في هذه الحالة قول نفس الشيء بالنسبة لعلاقة اللغات حرة البدايات مع الاوتومات القطعي . اي انه : لغة تُقبل بواسطة اوتومات دفع سفلي قطعي عن طريق فراغ المُكدس فقط اذا هي حرة السياق ويمكن ان تُقبل عن طريق اوتومات دفع سفلي قطعي (ربما اخر) عن طريق الوصول لحالة نهائية (وهذا يعني انه ليس كل لغة تُقبل عن الحالة النهائية يمكن أيضا أن تقبل عن طريق فراغ المُكدس لذا فالشرط أن اللغة حرة البدايات ضروري) .

قواعد حرة السياق قطعية[عدل]

وهي مجموعة اللغات التي تُقبل بواسطة اوتومات دفع سفلي قطعي عن طريق الوصول لحالة نهائية . ولها يُرمز DCF . وهذه المجموعة تحوي مجموعة اللغات النظامية (regular languages) على انها مجموعة جزئية فعلية اي  REG\subset DCF , وهذا لان الاوتومات ذو الحالات النهائية القطعي يمكن النظر اليه على انه اوتومات دفع سفلي قطعي يتجاهل المُكدس , وكذلك يمكن بناء اوتومات دفع سفلي قطعي بسهولة للغة غير النظامية  \{a^nba^n|n>1\} . مجموعة اللغات حرة السياق(يُرمز لها CF) تحوي هذه المجموعة فعليا اي :  DCF\subset CF .

انظر أيضا[عدل]

مصادر[عدل]