אוטומט מחסנית (PDA)

הגדרה פורמלית

PDA הוא שביעייה M = (Q, Σ, Γ, δ, q₀, Z₀, F):

• Q – קבוצה סופית של מצבים.
• Σ – אלפבית הקלט.
• Γ – אלפבית המחסנית (יכול להכיל סימנים מיוחדים שאינם בקלט).
• δ : Q × (Σ ∪ {ε}) × Γ → 𝒫(Q × Γ*) – פונקציית המעברים. בהינתן (מצב, אות בקלט או ε, סימן בראש המחסנית) מחזירה קבוצה של (מצב חדש, מחרוזת לכתוב במקום הסימן שהוצא).
• q₀ – מצב התחלתי.
• Z₀ ∈ Γ – סימן התחלתי בתחתית המחסנית.
• F – מצבים מקבלים.

PDA תמיד לא־דטרמיניסטי בהגדרתו (אחרת המודל חלש יותר). למרות זאת הסימולציה לא קשה.

פעולות המחסנית

• Push X – להוסיף את הסימן X לראש המחסנית. בכתיב המעבר: מחליפים את הסימן שבראש (נניח Y) ב־"XY" (Y נשאר תחתיו, X חדש למעלה).
• Pop – להסיר את הסימן העליון. בכתיב המעבר: מחליפים את Y שבראש ב־ε (מחרוזת ריקה).
• שמירה – להחליף Y ב־Y עצמו (כלומר לא לשנות את המחסנית).

איך PDA רץ?

בכל צעד המכונה מסתכלת על שלושה דברים: המצב הנוכחי, האות הבאה בקלט (או "כלום" – ε), והסימן בראש המחסנית. לפי δ היא בוחרת מעבר – משנה מצב, צורכת/לא צורכת אות, ומעדכנת את ראש המחסנית.

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

דוגמה: L = {aⁿbⁿ | n ≥ 0}

נבנה PDA שמזהה את השפה הקלאסית שאוטומט סופי לא מצליח. הרעיון: דוחפים A למחסנית עבור כל a שנקרא, ועבור כל b שנקרא – מוציאים A. אם הקלט נגמר ביחד עם המחסנית הריקה – התקבל.

סימון: "a, X / AX" פירושו: קוראים אות a, רואים את X בראש המחסנית, ומחליפים אותו ב־AX (כלומר Push A מעל X). "b, A / ε" פירושו Pop A.

ריצה על aabb

1. q₀, קלט aabb, מחסנית Z₀ — קוראים a, Push A → מחסנית: AZ₀
2. q₀, קלט abb, מחסנית AZ₀ — קוראים a, Push A → מחסנית: AAZ₀
3. q₀ → q₁ ב־ε — מחסנית: AAZ₀ (לא משתנה)
4. q₁, קלט bb, מחסנית AAZ₀ — קוראים b, Pop A → מחסנית: AZ₀
5. q₁, קלט b, מחסנית AZ₀ — קוראים b, Pop A → מחסנית: Z₀
6. q₁ → q₂ ב־ε — קלט נגמר, q₂ מקבל ⇒ התקבל.

PDA ושפות חסרות הקשר

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

חשוב: לא כל שפה ניתן לזהות ב־PDA. למשל {aⁿbⁿcⁿ} אינה חסרת הקשר (יש למת ניפוח גם ל־CFL).