آلة قائمة الانتظار

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

يمكن تعريف آلة الطابور بأنها مجموعة سداسية

${\displaystyle M=(Q,\Sigma ,\Gamma ,\$,s,\delta )}$أين

• ${\displaystyle \,Q}$هي مجموعة محدودة من الحالات ؛
• ${\displaystyle \,\Sigma \subset \Gamma }$هي المجموعة المحدودة من أبجدية الإدخال ؛
• ${\displaystyle \,\Gamma }$هي أبجدية قائمة الانتظار المحدودة ؛
• ${\displaystyle \,\$\in \Gamma \setminus \Sigma }$هو رمز الطابور الأولي ؛
• ${\displaystyle \,s\in Q}$هي حالة البداية ؛
• ${\displaystyle \,\delta :Q\times \Gamma \rightarrow Q\times \Gamma ^{*}}$هي دالة الانتقال .

تُعرَّف تهيئة الآلة بأنها زوج مرتب من حالتها ومحتويات قائمة الانتظار الخاصة بها${\displaystyle \,(q,\gamma )\in Q\times \Gamma ^{*}}$، أين${\displaystyle \,\Gamma ^{*}}$يشير إلى إغلاق كلين لـ${\displaystyle \,\Gamma }$التكوين الأولي لسلسلة الإدخال${\displaystyle \,x}$يُعرَّف بأنه${\displaystyle \,(s,x\$)}$والانتقال${\displaystyle \rightarrow _{M}^{1}}$يتم تعريف الانتقال من تكوين إلى آخر على النحو التالي:

${\displaystyle \,(p,A\alpha )\rightarrow _{M}^{1}(q,\alpha \gamma )}$

أين${\displaystyle A}$هو رمز من أبجدية الطابور،${\displaystyle \alpha }$هي سلسلة من رموز الطابور (${\displaystyle \alpha \in \Gamma ^{*}}$)، و${\displaystyle (q,\gamma )=\delta (p,A)}$لاحظ خاصية "الأول في الأول خارج" الخاصة بالطابور في العلاقة.

تقبل الآلة سلسلة نصية${\displaystyle \,x\in \Sigma ^{*}}$إذا تطور التكوين الأولي بعد عدد محدود من التحولات حتى استنفد السلسلة (الوصول إلى السلسلة الفارغة)${\displaystyle \,\epsilon }$أو على نحو آخر، إذا${\displaystyle \,(s,x\$)\rightarrow _{M}^{*}(q,\epsilon ).}$^{[ 2 ]}

توفر آلات الطوابير نموذجًا بسيطًا يمكن الاستناد إليه في تصميم بنى الحواسيب ، ^{[ 4 ] [ 5 ]} ولغات البرمجة ، أو الخوارزميات . ^{[ 6 ] [ 7 ]}

• قابلية الحوسبة
• مكافئات آلة تورينج
• الأوتوماتون الحتمي المحدود
• نظام الوسوم
• Manufactoria ، وهي لعبة فلاش للمتصفح تكلف اللاعب بتنفيذ خوارزميات مختلفة باستخدام نموذج آلة قائمة الانتظار.