אוטומט מחסנית

אוטומט מחסנית הוא מכונת מצבים המורחבת במחסנית — זיכרון לא־חסום מסוג נכנס־אחרון־יוצא־ראשון. בכל שלב ה־PDA קורא סמל קלט (או מבצע מעבר ε), שולף את סמל המחסנית העליון, ובהתאם לשלושתם עובר למצב חדש ודוחף אפס או יותר סמלים למחסנית. PDA מזהה בדיוק את השפות חופשיות־ההקשר.

סימולטור זה משתמש בקבלה לפי מצב סופי: מחרוזת מתקבלת אם, לאחר קריאת כל הקלט, ה־PDA נמצא באחד ממצבי הקבלה המיועדים (תוכן המחסנית אינו משנה). קבלה לפי מחסנית ריקה היא מודל שקול — כל שפה המתקבלת בדרך אחת ניתנת לקבלה בדרך האחרת — אך קבלה לפי מצב סופי נפוצה יותר בפועל.

מעבר ε מאפשר ל־PDA לשנות מצב, לשלוף סמל מהמחסנית ולדחוף סמלים חדשים בלי לקרוא אף תו קלט. סימולטור זה מנסה מעברי ε לפני קריאת סמל הקלט הבא ומזהה מעגלים כדי למנוע לולאות ε אינסופיות.

התווית "a,A/BC" משמעה: קרא קלט "a", שלוף "A" מראש המחסנית, ודחוף "BC" כאשר "B" הופך לראש החדש. דחיפה ריקה (הנכתבת ε) משמעה שליפה בלבד. התו השמאלי ביותר במחרוזת הדחיפה נדחף אחרון, ולכן הוא זה שנשאר בראש.

PDA מזהה את כל השפות חופשיות־ההקשר, המכילות ממש את השפות הרגולריות. דוגמאות קלאסיות הדורשות מחסנית הן {aⁿbⁿ | n ≥ 1} (מספר שווה של a ו־b) וסוגריים מאוזנים. עם זאת, PDA אינו יכול לזהות את כל השפות — {aⁿbⁿcⁿ} למשל דורש מכונת טיורינג.

כן — PDA ו־CFG שקולים בדיוק בכוח הביטוי שלהם. עבור כל CFG קיים PDA שמקבל את אותה שפה, ולהפך. שקילות זו יסודית: היא אומרת שניתן לעבור בחופשיות בין תיאור הדקדוק (כללי גזירה) לתיאור המכונה (מצבים + מחסנית) בעת חשיבה על שפות חופשיות־הקשר.

לא. כל שפה המזוהה על ידי DFA או NFA מזוהה גם על ידי PDA (שכן השפות הרגולריות הן תת־קבוצה של השפות חופשיות־ההקשר), אך ההפך אינו נכון. PDA יכול לזהות את {aⁿbⁿ} וסוגריים מאוזנים, שאף DFA או NFA אינם יכולים. המחסנית מעניקה ל־PDA זיכרון רב יותר ממש מהבקרה הסופית של DFA/NFA.

לא — מכונת טיורינג חזקה ממש יותר. למכונת טיורינג יש סרט קריאה/כתיבה לא־חסום שניתן לנוע עליו בשני הכיוונים, בעוד של־PDA יש רק מחסנית (נכנס־אחרון־יוצא־ראשון). שפות כמו {aⁿbⁿcⁿ} מעבר ליכולתו של כל PDA אך כריעות על ידי מכונת טיורינג. מכונות טיורינג יכולות לחשב כל דבר הניתן לחישוב אלגוריתמי; PDA מוגבל לשפות חופשיות־ההקשר.