آلة الضغط لأسفل

أنواع الأوتوماتا

في نظرية الحوسبة ، وهي فرع من فروع علوم الحاسوب النظرية ، فإن آلة الدفع لأسفل ( PDA ) هي نوع من الآلات التي تستخدم مكدسًا .

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

يشير مصطلح "الدفع للأسفل" إلى إمكانية اعتبار المكدس "مدفوعًا للأسفل" كجهاز توزيع الصواني في الكافيتريا، حيث لا تُجرى العمليات إلا على العنصر العلوي. في المقابل، يسمح أوتومات المكدس بالوصول إلى العناصر الأعمق وإجراء العمليات عليها. كما يمكن لأوتومات المكدس التعرف على مجموعة أكبر من اللغات مقارنةً بأوتومات الدفع للأسفل. ^{[ 1 ]} يتيح أوتومات المكدس المتداخل الوصول الكامل، كما يسمح بأن تكون القيم المكدسة عبارة عن مكدسات فرعية كاملة بدلاً من مجرد رموز محدودة مفردة.

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

1. يمكنه استخدام الجزء العلوي من المكدس لتحديد الانتقال الذي يجب القيام به.
2. يمكنه التلاعب بالمكدس كجزء من تنفيذ عملية الانتقال.

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

عند الجمع بين كل شيء: بالنظر إلى رمز الإدخال والحالة الحالية ورمز المكدس، يمكن للآلة أن تتبع الانتقال إلى حالة أخرى، ويمكنها اختيارياً التلاعب بالمكدس (دفع أو سحب).

إذا كان من الممكن، في كل حالة، إجراء انتقال واحد على الأكثر، يُطلق على الآلة اسم آلة دفع تنازلية حتمية (DPDA) . عمومًا، إذا كان من الممكن إجراء عدة عمليات، تُسمى الآلة آلة دفع تنازلية عامة ، أو غير حتمية . قد تُوجه سلسلة إدخال مُعطاة آلة دفع تنازلية غير حتمية إلى إحدى تسلسلات التكوين المتعددة؛ إذا أدى أحدها إلى تكوين مقبول بعد قراءة سلسلة الإدخال كاملة، يُقال إن هذا التكوين ينتمي إلى اللغة التي تقبلها الآلة .

نستخدم رموز اللغة الرسمية القياسية:${\displaystyle \Gamma ^{*}}$يشير إلى مجموعة السلاسل ذات الطول المحدود على الأبجدية${\displaystyle \Gamma }$و${\displaystyle \varepsilon }$يشير إلى السلسلة الفارغة .

يُعرَّف جهاز الدفع الآلي (PDA) رسميًا بأنه مجموعة من 7 عناصر:

${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Z,F)}$ أين

• ${\displaystyle Q}$هي مجموعة محدودة من الحالات
• ${\displaystyle \Sigma }$هي مجموعة منتهية تسمى أبجدية الإدخال
• ${\displaystyle \Gamma }$هي مجموعة منتهية تسمى أبجدية المكدس
• ${\displaystyle \delta }$هي مجموعة جزئية منتهية من${\displaystyle Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}}$، علاقة الانتقال
• ${\displaystyle q_{0}\in Q}$هي حالة البداية
• ${\displaystyle Z\in \Gamma }$هو رمز المكدس الأولي
• ${\displaystyle F\subseteq Q}$هي مجموعة الحالات المقبولة

عنصر${\displaystyle (p,a,A,q,\alpha )\in \delta }$هو انتقال من${\displaystyle M}$. له المعنى المقصود وهو${\displaystyle M}$، في الولاية${\displaystyle p\in Q}$، على المدخل${\displaystyle a\in \Sigma \cup \{\varepsilon \}}$ومع${\displaystyle A\in \Gamma }$كرمز أعلى المكدس، يمكن قراءته${\displaystyle a}$، غيّر الحالة إلى${\displaystyle q}$، موسيقى البوب${\displaystyle A}$، واستبداله بالضغط${\displaystyle \alpha \in \Gamma ^{*}}$. ال${\displaystyle (\Sigma \cup \{\varepsilon \})}$يُستخدم عنصر من علاقة الانتقال لإضفاء الطابع الرسمي على أن جهاز PDA يمكنه إما قراءة حرف من المدخلات، أو المتابعة مع ترك المدخلات دون تغيير.

في العديد من النصوص ^{[ 2 ]} يتم استبدال علاقة الانتقال بصياغة رسمية (مكافئة)، حيث

• ${\displaystyle \delta }$هي دالة الانتقال ، عملية التعيين${\displaystyle Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma }$إلى مجموعات جزئية منتهية من${\displaystyle Q\times \Gamma ^{*}}$

هنا${\displaystyle \delta (p,a,A)}$يحتوي على جميع الإجراءات الممكنة في الحالة${\displaystyle p}$مع${\displaystyle A}$على المكدس، أثناء القراءة${\displaystyle a}$في المدخلات. يكتب المرء على سبيل المثال${\displaystyle \delta (p,a,A)=\{(q,BA)\}}$متى بالضبط${\displaystyle (q,BA)\in \{(q,BA)\},(q,BA)\in \delta (p,a,A),}$لأن${\displaystyle ((p,a,A),\{(q,BA)\})\in \delta }$لاحظ أن كلمة "محدود" في هذا التعريف ضرورية.

الحسابات

لإضفاء الطابع الرسمي على دلالات آلة الدفع لأسفل، يتم تقديم وصف للوضع الحالي. أي ثلاثية${\displaystyle (p,w,\beta )\in Q\times \Sigma ^{*}\times \Gamma ^{*}}$يُطلق عليه وصف فوري (ID) لـ${\displaystyle M}$والتي تشمل الحالة الحالية، وجزء شريط الإدخال الذي لم تتم قراءته، ومحتويات المكدس (الرمز العلوي مكتوب أولاً). علاقة الانتقال${\displaystyle \delta }$يحدد علاقة الخطوة${\displaystyle \vdash _{M}}$ل${\displaystyle M}$حول الأوصاف الفورية. للتعليمات${\displaystyle (p,a,A,q,\alpha )\in \delta }$توجد خطوة${\displaystyle (p,ax,A\gamma )\vdash _{M}(q,x,\alpha \gamma )}$لكل${\displaystyle x\in \Sigma ^{*}}$وكل${\displaystyle \gamma \in \Gamma ^{*}}$.

بشكل عام، تكون آلات الدفع لأسفل غير حتمية، مما يعني أنه في وصف لحظي معين${\displaystyle (p,w,\beta )}$قد توجد عدة خطوات ممكنة. يمكن اختيار أيٍّ من هذه الخطوات في عملية حسابية. وفقًا للتعريف المذكور أعلاه، في كل خطوة، يُزال رمز واحد (أعلى المكدس) ويُستبدل بعدد الرموز اللازمة. ونتيجةً لذلك، لا تُحدَّد أي خطوة عندما يكون المكدس فارغًا.

تُعدّ عمليات حساب آلة الدفع السفلي عبارة عن تسلسلات من الخطوات. تبدأ عملية الحساب في الحالة الابتدائية.${\displaystyle q_{0}}$مع رمز المكدس الأولي${\displaystyle Z}$على المكدس، وسلسلة نصية${\displaystyle w}$على شريط الإدخال - وبالتالي، مع الوصف الأولي${\displaystyle (q_{0},w,Z)}$.

هناك نمطان للقبول. يقبل جهاز الدفع السفلي إما عن طريق الحالة النهائية، مما يعني أنه بعد قراءة مدخلاته، يصل الجهاز إلى حالة قبول (في${\displaystyle F}$أو يقبلها عن طريق مكدس فارغ (${\displaystyle \varepsilon }$وهذا يعني أنه بعد قراءة مدخلاته، يقوم الجهاز الآلي بتفريغ مكدسه. يستخدم نمط القبول الأول الذاكرة الداخلية (الحالة)، بينما يستخدم الثاني الذاكرة الخارجية (المكدس).

يُعرّف المرء رسميًا

1. ${\displaystyle L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )}$مع${\displaystyle f\in F}$و${\displaystyle \gamma \in \Gamma ^{*}\}}$(الحالة النهائية)
2. ${\displaystyle N(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(q,\varepsilon ,\varepsilon )}$مع${\displaystyle q\in Q\}}$(مجموعة فارغة)

هنا${\displaystyle \vdash _{M}^{*}}$يمثل الإغلاق الانعكاسي والمتعدي لعلاقة الخطوة${\displaystyle \vdash _{M}}$، بمعنى أي عدد من الخطوات المتتالية (صفر، واحد أو أكثر).

بالنسبة لكل آلة دفع سفلية، لا يشترط وجود علاقة بين هاتين اللغتين؛ قد تكونان متطابقتين، ولكن هذا ليس هو الحال عادةً. يجب أن يتضمن وصف الآلة أيضًا طريقة القبول المقصودة. عند تطبيقها على جميع آلات الدفع السفلية، تُعرّف شروط القبول نفسها عائلة اللغات ذاتها.

نظرية. لكل آلة دفع لأسفل${\displaystyle M}$يمكن للمرء أن يبني آلة دفع لأسفل${\displaystyle M'}$بحيث${\displaystyle L(M)=N(M')}$والعكس صحيح، لكل آلة دفع لأسفل${\displaystyle M}$يمكن للمرء أن يبني آلة دفع لأسفل${\displaystyle M'}$بحيث${\displaystyle N(M)=L(M')}$

فيما يلي الوصف الرسمي لجهاز المساعد الرقمي الشخصي الذي يتعرف على اللغة${\displaystyle \{0^{n}1^{n}\mid n\geq 0\}}$حسب الحالة النهائية:

${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)}$، أين

• الولايات:${\displaystyle Q=\{p,q,r\}}$
• أبجدية الإدخال:${\displaystyle \Sigma =\{0,1\}}$
• الأبجدية المكدسة:${\displaystyle \Gamma =\{A,Z\}}$
• حالة البداية:${\displaystyle q_{0}=p}$
• رمز بداية المكدس: Z
• الولايات المقبولة:${\displaystyle F=\{r\}}$

علاقة الانتقال${\displaystyle \delta }$يتكون من التعليمات الست التالية:

${\displaystyle (p,0,Z,p,AZ)}$،

${\displaystyle (p,0,A,p,AA)}$،

${\displaystyle (p,\epsilon ,Z,q,Z)}$،

${\displaystyle (p,\epsilon ,A,q,A)}$،

${\displaystyle (q,1,A,q,\epsilon )}$، و

${\displaystyle (q,\epsilon ,Z,r,Z)}$.

بعبارة أخرى، تنص التعليمات الأولى والثانية على أنه في الحالة p في أي وقت يكون الرمزعند قراءة 0 ، يتم دفع رمز A واحد إلى المكدس. يتم صياغة دفع الرمز A فوق رمز A آخر على أنه استبدال الرمز A العلوي بـ AA (وبالمثل لدفع الرمز A فوق الرمز Z ).

وتقول التعليمات الثالثة والرابعة أنه في أي لحظة يمكن للآلة أن تنتقل من الحالة p إلى الحالة q .

تنص التعليمات الخامسة على أنه في الحالة q ، لكل رمزتمت قراءة حرف واحد ، وتم فصل حرف A واحد.

أخيرًا، تنص التعليمات السادسة على أنه لا يمكن للجهاز الانتقال من الحالة q إلى حالة القبول r إلا عندما يكون الرمز Z هو رمز أعلى المكدس. في هذا الجهاز الآلي ذي المكدس القابل للبرمجة، يُعادل ذلك وجود رمز Z واحد فقط في المكدس ، حيث يُستخدم Z فقط كعلامة أسفل المكدس، ولا يوجد انتقال يدفع رمز Z آخر فوقه.

يبدو أنه لا يوجد تمثيل شائع الاستخدام للأجهزة المساعدة الرقمية الشخصية (PDA). هنا قمنا بتوضيح التعليمات.${\displaystyle (p,a,A,q,\alpha )}$بواسطة حافة من الحالة p إلى الحالة q التي تحمل علامة ${\displaystyle a;A/\alpha }$(اقرأ a من سلسلة الإدخال؛ استبدل A في أعلى المكدس بـ${\displaystyle \alpha }$).

توضيح

يوضح ما يلي كيفية حساب PDA المذكور أعلاه على سلاسل إدخال مختلفة. يشير الرمز السفلي M من رمز الخطوة${\displaystyle \vdash }$تم حذفه هنا.

1. سلسلة الإدخال = 0011. هناك حسابات مختلفة، تعتمد على لحظة الانتقال من الحالة p إلى الحالة q . واحدة فقط من هذه الحسابات مقبولة.
   1. ${\displaystyle (p,0011,Z)\vdash (q,0011,Z)\vdash (r,0011,Z)}$الحالة النهائية هي القبول، ولكن المدخلات لا تُقبل بهذه الطريقة لأنها لم تُقرأ.
   2. ${\displaystyle (p,0011,Z)\vdash (p,011,AZ)\vdash (q,011,AZ)}$لا توجد خطوات أخرى ممكنة.
   3. ${\displaystyle (p,0011,Z)\vdash (p,011,AZ)\vdash (p,11,AAZ)\vdash (q,11,AAZ)\vdash (q,1,AZ)\vdash (q,\epsilon ,Z)\vdash (r,\epsilon ,Z)}$قبول الحساب: ينتهي بقبول الحالة، بينما تمت قراءة المدخلات بالكامل.
2. سلسلة الإدخال = 00111. هناك عمليات حسابية مختلفة، لكن لا يوجد أي منها مقبول.
   1. ${\displaystyle (p,00111,Z)\vdash (q,00111,Z)\vdash (r,00111,Z)}$الحالة النهائية هي القبول، ولكن المدخلات لا تُقبل بهذه الطريقة لأنها لم تُقرأ.
   2. ${\displaystyle (p,00111,Z)\vdash (p,0111,AZ)\vdash (q,0111,AZ)}$لا توجد خطوات أخرى ممكنة.
   3. ${\displaystyle (p,00111,Z)\vdash (p,0111,AZ)\vdash (p,111,AAZ)\vdash (q,111,AAZ)\vdash (q,11,AZ)\vdash (q,1,Z)\vdash (r,1,Z)}$الحالة النهائية هي القبول، ولكن المدخلات لا يتم قبولها بهذه الطريقة لأنها لم تتم قراءتها (بشكل كامل).

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

من الناحية الفنية، بالنظر إلى قواعد اللغة الخالية من السياق، فإن آلة الدفع الآلي لها حالة واحدة، وهي 1، ويتم بناء علاقة الانتقال الخاصة بها على النحو التالي.

1. ${\displaystyle (1,\varepsilon ,A,1,\alpha )}$لكل قاعدة${\displaystyle A\to \alpha }$( يوسع )
2. ${\displaystyle (1,a,a,1,\varepsilon )}$لكل رمز طرفي${\displaystyle a}$( مباراة )

يقبل جهاز PDA مكدسًا فارغًا. رمز المكدس الأولي الخاص به هو رمز بداية القواعد النحوية. ^{[ 3 ]}

بالنسبة لقواعد اللغة الخالية من السياق في شكل غريباخ الطبيعي ، فإن تعريف (1،γ) ∈ δ(1، a ، A ) لكل قاعدة نحوية A → a γ ينتج عنه أيضًا آلة دفع غير حتمية مكافئة. ^{[ 4 ]}

أما عكس ذلك، أي إيجاد قواعد نحوية لآلة دفعية معينة، فليس بالأمر السهل. تكمن الحيلة في ترميز حالتين من حالات الآلة الدفعية في الرموز غير الطرفية للقواعد النحوية.

نظرية. لكل آلة دفع لأسفل${\displaystyle M}$يمكن للمرء أن يبني قواعد نحوية خالية من السياق${\displaystyle G}$بحيث${\displaystyle N(M)=L(G)}$[ ^{5 ]​}

تُسمى لغة السلاسل التي يقبلها جهاز الدفع الحتمي (DPDA) لغة حتمية خالية من السياق . ليست كل اللغات الخالية من السياق حتمية. ^{[ أ ]} ونتيجة لذلك، يُعد جهاز الدفع الحتمي (DPDA) شكلاً أضعف من جهاز الدفع الآلي (PDA). حتى بالنسبة للغات المنتظمة ، توجد مشكلة تضخم الحجم: لأي دالة تكرارية${\displaystyle f}$وبالنسبة للأعداد الصحيحة الكبيرة بشكل تعسفي${\displaystyle n}$يوجد جهاز مساعد رقمي شخصي بحجم${\displaystyle n}$وصف لغة منتظمة يكون أصغر جهاز DPDA فيها على الأقل${\displaystyle f(n)}$^[ ب ^{] بالنسبة للعديد من أجهزة PDA غير المنتظمة، فإن} أي جهاز DPDA مكافئ سيتطلب عددًا غير محدود من الحالات.

الآلة المحدودة التي يمكنها الوصول إلى مكدسين هي جهاز أكثر قوة، تعادل في قوتها آلة تورينج . ^{[ 8 ]} الآلة المحدودة الخطية هي جهاز أقوى من آلة الدفع لأسفل، ولكنها أقل قوة من آلة تورينج. ^{[ ج ]}

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

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

الآلة الآلية العامة للدفع لأسفل (GPDA) هي آلة آلية للدفع لأسفل تقوم بكتابة سلسلة كاملة ذات طول معروف إلى المكدس أو إزالة سلسلة كاملة من المكدس في خطوة واحدة.

يُعرَّف GPDA رسميًا بأنه مجموعة من 6 عناصر:

${\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)}$

أين${\displaystyle Q,\Sigma \,,\Gamma \,,q_{0}}$و​${\displaystyle F}$يتم تعريفها بنفس طريقة تعريف جهاز المساعد الرقمي الشخصي (PDA).

${\displaystyle \,\delta }$:${\displaystyle Q\times \Sigma _{\epsilon }\times \Gamma ^{*}\longrightarrow P(Q\times \Gamma ^{*})}$

هي دالة الانتقال.

قواعد الحساب لآلة الأوتوماتا العامة (GPDA) هي نفسها قواعد الحساب لآلة الأوتوماتا المحدودة (PDA) باستثناء أن${\displaystyle a_{i+1}}$'رمل${\displaystyle b_{i+1}}$أصبحت الآن عبارة عن سلاسل نصية بدلاً من رموز.

تتشابه آلات الدفع لأسفل وآلات الدفع لأسفل المعممة من حيث أنه إذا تم التعرف على لغة ما بواسطة آلة الدفع لأسفل، فسيتم التعرف عليها أيضًا بواسطة آلة الدفع لأسفل المعممة، والعكس صحيح.

يمكن صياغة برهان تحليلي لتكافؤ آلات الدفع السفلي وآلات الدفع السفلي المعممة باستخدام المحاكاة التالية:

يترك${\displaystyle \delta (q_{1},w,x_{1}x_{2}\cdot x_{m})\longrightarrow (q_{2},y_{1}y_{2}...y_{n})}$أن يكون انتقالاً لقانون حماية البيانات العامة، حيث:

${\displaystyle q_{1},q_{2}\in Q,w\in \Sigma _{\epsilon },x_{1},x_{2},\ldots ,x_{m}\in \Gamma ^{*},m\geq 0,y_{1},y_{2},\ldots ,y_{n}\in \Gamma ^{*},n\geq 0}$

قم بإنشاء الانتقالات التالية لآلة الدفع الآلي (PDA):

${\displaystyle {\begin{array}{lcl}\delta '(q_{1},w,x_{1})&\longrightarrow &(p_{1},\epsilon )\\\delta '(p_{1},\epsilon ,x_{2})&\longrightarrow &(p_{2},\epsilon )\\&\vdots &\\\delta '(p_{m-1},\epsilon ,x_{m})&\longrightarrow &(p_{m},\epsilon )\\\delta '(p_{m},\epsilon ,\epsilon )&\longrightarrow &(p_{m+1},y_{n})\\\delta '(p_{m+1},\epsilon ,\epsilon )&\longrightarrow &(p_{m+2},y_{n-1})\\&\vdots &\\\delta '(p_{m+n-1},\epsilon ,\epsilon )&\longrightarrow &(q_{2},y_{1}).\end{array}}}$

كتعميم لآلات الدفع السفلي، درس جينسبيرغ، وغريباخ، وهاريسون (1967) آلات المكدس ، التي يمكنها أيضًا التحرك يمينًا أو يسارًا في سلسلة الإدخال (محاطة برموز علامات نهاية خاصة لمنع الانزلاق)، والتحرك لأعلى أو لأسفل في المكدس في وضع القراءة فقط. ^{[ 11 ] [ 12 ]} تُسمى آلة المكدس غير ماسحة إذا لم تقم أبدًا بسحب عنصر من المكدس. فئة اللغات التي تقبلها آلات المكدس غير الحتمية وغير الماسحة هي NSPACE ( n² ⁾ ، وهي مجموعة شاملة للغات الحساسة للسياق . ^{[ 1 ]} فئة اللغات التي تقبلها آلات المكدس الحتمية وغير الماسحة هي DSPACE ( n ⋅ log( n )). ^{[ 1 ]}

آلة الدفع التناوبي (APDA) هي آلة دفع ذات مجموعة حالات

• ${\displaystyle Q=Q_{\exists }\cup Q_{\forall }}$أين${\displaystyle Q_{\exists }\cap Q_{\forall }=\emptyset }$.

الولايات في${\displaystyle Q_{\exists }}$و${\displaystyle Q_{\forall }}$تُسمى هذه الحالات بالوجودية والشمولية على التوالي . في الحالة الوجودية، يختار خوارزمية APDA الحالة التالية بشكل غير حتمي، ويقبلها إذا قبلتها إحدى العمليات الحسابية الناتجة على الأقل . أما في الحالة الشمولية، فتنتقل خوارزمية APDA إلى جميع الحالات التالية، وتقبلها إذا قبلتها جميع العمليات الحسابية الناتجة.

تم تقديم هذا النموذج بواسطة تشاندرا وكوزين وستوكمير . ^{[ 13 ]} أثبت لادنر وليبتون وستوكمير ^{[ 14 ]} أن هذا النموذج مكافئ لـ EXPTIME، أي أن اللغة مقبولة بواسطة APDA إذا وفقط إذا كان من الممكن تحديدها بواسطة خوارزمية ذات وقت أسي.

قدم أيزيكوفيتز وكامينسكي ^{[ 15 ]} آلات الدفع المتناوبة المتزامنة (SAPDA) التي تعادل القواعد النحوية الاقترانية بنفس الطريقة التي تعادل بها آلات الدفع غير الحتمية القواعد النحوية الخالية من السياق.

• قواعد اللغة الخالية من السياق
• نظام مضاد آلي
• آلة الحالة المحدودة
• آلة قائمة الانتظار
• آلة تكديس