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

في علم الحاسوب، الأوتومات الدفع السفلي أو باختصار "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)$ حيث يتحقق:

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$ ، كما هو مبين في الصورة.

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\neq \lambda$ وكذلك $A\neq A'$ أي أن الاختيار يكون حسب رأس المكدس العلوي وخلاف هذا الصورتين الفوريتين متساويتين.

لغات الأوتومات القطعي

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

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

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

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

انظر أيضا

• آلة تورنغ
• آلة الحالات المحدودة