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

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

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

ملاحظات :

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

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

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

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

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

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

1. لغة الحالة النهائية للأوتومات ${\displaystyle {\mathcal {A}}}$ هي: ${\displaystyle 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. لغة المُكدس الفارغ للاتومات ${\displaystyle {\mathcal {A}}}$ هي: ${\displaystyle N({\mathcal {A}})=\{x\in \Delta ^{*}|(x,q_{in},A_{in})\vdash _{\mathcal {A}}^{*}(\lambda ,q,\lambda )\ {\mbox{for some}}\ q\in Q\}}$

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

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

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

• ${\displaystyle (q,\lambda ,A,q,\alpha )}$ لكل ${\displaystyle A\to \alpha \in P}$ . «توسيع»
• ${\displaystyle (q,a,a,q,\lambda )}$ لكل ${\displaystyle a\in T}$ . «تطابق»

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

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

فلتكن A , B لغتين اللتين تُمَيَّزَان (recognized) بواسطة اوتماتي الدفع السفلي ${\displaystyle M_{A},M_{B}}$ على التوالي.

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

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

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

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

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

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

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

• بوابة علم الحاسوب
• بوابة تقنية المعلومات