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

ייצוג גרפי של אוטומט מחסנית, באמצעות גרף מכוון. האוטומט מורכב מ-4 מצבים: שני מצבים מקבלים (מסומנים בעיגול כפול) ושני מצבים שאינם מקבלים (מסומנים בעיגול בודד).

במדעי המחשב, אוטומט מחסנית (באנגלית: Pushdown automaton, ובראשי תיבות: PDA) הוא מודל חישובי, שמהווה הרחבה של מודל האוטומט הסופי (הדטרמיניסטי), על ידי הוספת מחסנית, שבה האוטומט מסוגל לאחסן מידע (משמע, לאוטומט יש יכולת זיכרון). ההרחבה מגדילה את כוחו החישובי של האוטומט; כלומר, את קבוצת השפות שהוא מסוגל לזהות. בגרסתו הסטנדרטית, מודל אוטומט המחסנית מסוגל לזהות בדיוק את כל השפות חסרות ההקשר.

תיאור לא פורמלי

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

ההבדל המרכזי שבין אוטומט סופי ובין אוטומט מחסנית הוא התקן הזיכרון הנוסף, שעומד לרשות אוטומט המחסנית – מחסנית, שמאפשרת אחסון (שמירת) נתונים. המחסנית מאחסנת אותיות (מעל אלפבית סופי וידוע מראש, אך לא בהכרח האלפבית שממנו בנויה מילת הקלט) בצורה סדרתית, כך שהאות האחרונה שהוכנסה למחסנית נמצאת בראשה, אחריה האות שהוכנסה לפניה למחסנית, וכן הלאה, עד האות הראשונה שהוכנסה למחסנית, הנמצאת בתחתיתה (ונגישה להצצה או שליפה אחרונה מכולן) (שיטת LIFO). בצורה זו, הגישה לזיכרון מוגבלת מאוד – ניתן לראות בכל פעם רק את האות שבראש המחסנית, וכדי לראות אות שבתוך המחסנית, יש להוציא מהמחסנית את כל האותיות שמעליה (ובכך "לאבד" אותן, שכן אין מקום אחסון נוסף עבורן).

ביצוע חישוב

בכל צעד חישוב שלו, אוטומט המחסנית מחליט על דרך הפעולה שלו, בהתבסס על שלושה נתונים:

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

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

• הוצאת אות אחת בלבד מראש המחסנית (באנגלית, פעולת Pop).
• אי-ביצוע כל שינוי במחסנית (לא הכנסה ולא הוצאה של אותיות; משמע, רק "הצצנו"/הסתכלנו על האות שבראש המחסנית).
• דחיפת (הכנסת) לתוכה במקומה אותיות אחרות (באנגלית, פעולת Push).

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

אוטומט עם שתי מחסניות שקול בכוחו החישובי לזה של מכונת טיורינג.

תיאור פורמלי

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

תיאור מתמטי פורמלי של אוטומט מחסנית $\ A$ הוא באמצעות השביעייה הסדורה הבאה:

$\ A=\left\{Q,\Sigma ,\Gamma ,\delta ,q_{0},\dashv ,F\right\}$

כאשר:

• $Q$ היא קבוצת מצבי האוטומט. כל מצב בקבוצה זו הוא, בהכרח, אחד מהשניים: "מצב מקבל" או "מצב לא מקבל".
• $\Sigma$ היא (קבוצת) א"ב הקלט. כל איבר בקבוצה זו מכונה "אות".
• $\Gamma$ היא (קבוצת) א"ב של המחסנית. כל איבר בקבוצה זו מכונה "אות".
• $\delta \colon Q\times \left(\Sigma \cup \left\{\varepsilon \right\}\right)\times \Gamma \to \mathrm {P} \left(Q\times \Gamma ^{*}\right)$ היא פונקציית המעברים.
• $q_{0}$ הוא המצב ההתחלתי (ממנו מתחיל החישוב) $q_{0}\in Q$.
• $\dashv$ היא האות ההתחלתית שבמחסנית - תמיד! זוהי אות שמורה מיוחדת, שמשמעותה בפועל היא שהמחסנית ריקה, כי למחסנית ריקה באמת יש משמעות מעשית אחרת באוטומט מחסנית.
• $F$ היא קבוצת המצבים המקבלים, $F\subseteq Q$. מצב מקבל הוא מצב שמסמן שהאוטומט מחזיר תשובה חיובית. כלומר: אם בסוף הקלט האוטומט נמצא במצב מקבל, זה אומר שהקלט הוא מילה בשפה שהאוטומט מזהה.

משמעותה של פונקציית המעברים היא זו – בהינתן:

• המצב הנוכחי של האוטומט (שם המצב),
• האות הבאה שהוא קורא מהקלט (או המילה הריקה $\varepsilon$, אם רוצים לתאר מעבר, שאינו כולל קריאת מילה מהקלט),
• האות שמופיעה בראש המחסנית,

פעולת האוטומט תהיה לעבור למצב אחר (או להישאר במצב שבו הוא נמצא), ולשנות את תוכן המחסנית על ידי הסרת האות שנמצאת בראש המחסנית והכנסת אות או מילה חדשה במקומה למחסנית (ייתכן, אפילו, להכניס את אותה האות שהוצאה, על-מנת לא לשנות את מצב המחסנית).

מכיוון שהאוטומט אי-דטרמיניסטי, לכל שלשה סדורה של: מצב + אות קלט + אות מראש המחסנית, מותאמת קבוצה של זוגות סדורים אפשריים, שכל אחד מהם מורכב מ: המצב שאליו עוברים + המילה שמוכנסת לראש המחסנית (יכולה להיות גם המילה הריקה $\ \varepsilon$; דהיינו, לא להכניס אף אות למחסנית). לכן, טווח פונקציית המעברים הוא $\mathrm {P} \left(Q\times \Gamma ^{*}\right)$ – קבוצת החזקה של כל הזוגות האפשריים של מצב + המילה המוכנסת לראש המחסנית. עם זאת, מניחים כי רק תת-הקבוצות הסופיות של זוגות שכאלו יכולים להתקבל באמצעות פונקציית המעברים (כלומר, מספר דרכי הפעולה השונות של האוטומט, בהינתן מצב, אות קלט ואות מראש המחסנית הוא סופי).

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

להלן מספר דוגמאות לפעולת פונקציית המעברים $\delta$ (הפועלת על שלשה סדורה ומחזירה זוג סדור), שבכולן האוטומט מתחיל במצב $q$ ונשאר בו:

• $(q,Z)\in \delta (q,\sigma ,Z)$ - האוטומט קורא את האות $\sigma$ מהקלט ואינו משנה את ראש המחסנית (ניתן לחשוב על כך כאילו האוטומט הוציא את האות $Z$ מראש המחסנית ומיד הכניס אותה בחזרה).
• $(q,\sigma Z)\in \delta (q,\sigma ,Z)$ - האוטומט קורא את האות $\ \sigma$ מהקלט ודוחף אותה למחסנית, מעל ראש המחסנית הקיים (ניתן לחשוב על כך כאילו האוטומט הוציא את האות $Z$ מראש המחסנית ומיד דחף אותה חזרה, ואחריה דחף גם את האות $\ \sigma$).
• $(q,\varepsilon )\in \delta (q,\sigma ,Z)$ - האוטומט קורא את האות $\ \sigma$ מהקלט ומוציא את האות $Z$ מראש המחסנית, מבלי לדחוף למחסנית שום דבר אחר במקומה. בכך, נחשפת האות שמתחתיה (זו שהוכנסה ממש לפני האות $Z$ למחסנית) ומהווה את ראש המחסנית החדש.

תיאור חישוב

על מנת לתאר חישובים באמצעות אוטומט מחסנית, נהוג להשתמש בתיאור רגעי. תיאור רגעי הוא שלשה סדורה, שמכילה את כל המידע הנחוץ לחישוב הצעד הנוכחי (והצעדים הנותרים) של האוטומט:

• המצב הנוכחי של האוטומט (שם המצב),
• שארית מילת הקלט (החלק שטרם נקרא),
• מצב המחסנית המלא.

בצורה פורמלית, מגדירים תיאור רגעי בתור השלשה הסדורה $\left(q,w,\gamma \right)$, כך ש:

• $\ q\in Q$ הוא המצב הנוכחי,
• $\ w\in \Sigma ^{*}$ היא מילת הקלט שטרם נקראה,
• $\ \gamma \in \Gamma ^{*}$ הוא תוכנהּ הנוכחי של המחסנית.

באמצעות תיאורים רגעיים, ניתן להציג חישוב של אוטומט מחסנית כסדרה של תיאורים רגעיים, שהמעבר בין כל שניים מהם מייצג צעד חישוב אחד של האוטומט. בצורה פורמלית, נהוג לסמן: $\left(q,aw,Z\alpha \right)\vdash \left(p,w,\beta \alpha \right)$, כדי לתאר מעבר מהמצב הרגעי $(q,aw,Z\alpha )$ למצב הרגעי $\left(p,w,\beta \alpha \right)$. מעבר כזה הוא אפשרי אם ורק אם $(p,\beta )\in \delta (q,a,Z)$ (כאן, $a\in \Sigma ^{*}$, ולכן ייתכן גם ש- $\ a=\varepsilon$).

בדומה, משתמשים בסימון $\vdash ^{k}$ כדי לתאר מעבר בן $\ k$ צעדים בין שני תיאורים רגעיים, ובסימן $\vdash ^{*}$ כדי לסמן שני תיאורים רגעיים, שניתן להגיע מהאחד אל השני במספר כלשהו של צעדים.

הגדרת קבלה

בדומה לאוטומט סופי, גם באוטומט מחסנית ניתן להגדיר קבלה של מילה באמצעות קבוצה של מצבים מקבלים: האוטומט יקבל מילה, אם לאחר סיום קריאת המילה (וייתכן שגם ביצוע מספר מסעי אפסילון ($\varepsilon$) לאחר מכן) האוטומט נמצא (עצר) במצב מקבל. עם זאת, קיימת דרך נוספת להגדיר קבלה עבור אוטומט מחסנית – קבלה באמצעות ריקון המחסנית. באופן קבלה זה, אומרים שהאוטומט מקבל מילה, אם לאחר סיום קריאת המילה (ושוב, ייתכן שגם ביצוע מספר מסעי אפסילון לאחר מכן) המחסנית ריקה (כזכור, אם המחסנית מתרוקנת לחלוטין (כולל האות המיוחדת השמורה $\ \dashv$) במהלך חישוב, הדבר גורם ל"תקיעת" האוטומט).

בצורה פורמלית, השפה שמתקבלת על ידי הגעה למצב מקבל מוגדרת בתור:

• $L_{f}(M)=\left\{w\in \Sigma ^{*}\mid \exists p\in F,\gamma \in \Gamma ^{*}:\left(q_{0},w,\dashv \right)\vdash ^{*}\left(p,\varepsilon ,\gamma \right)\right\}$

ואילו השפה שמתקבלת על ידי ריקון המחסנית מוגדרת בתור:

• $L_{e}(M)=\left\{w\in \Sigma ^{*}\mid \exists p\in Q:\left(q_{0},w,\dashv \right)\vdash ^{*}\left(p,\varepsilon ,\varepsilon \right)\right\}$

באופן כללי, יכול להיות ש- $L_{f}(M)\neq L_{e}(M)$; כלומר, שהשפה שהאוטומט מזהה על ידי הגעה למצב מקבל שונה מהשפה שהוא מזהה על ידי ריקון המחסנית. עם זאת, קיימת שקילות בין שני אופני הקבלה: אם שפה כלשהי $L$ מזוהה על ידי הגעה למצב מקבל בידי אוטומט מחסנית כלשהו, קיים אוטומט מחסנית (לא בהכרח אותו אחד) שמזהה את השפה $L$ על ידי ריקון המחסנית, ולהפך. כמובן, שניתן גם להגדיר את השפה שהאוטומט מקבל כאיחוד שתי דרכי הגדרות הקבלה: $L_{f}(M)\cup L_{e}(M)$.

לקריאה נוספת

• שמואל זקס ונסים פרנסיז, ‏אוטומטים ושפות פורמליות א, האוניברסיטה הפתוחה, 2000 (הספר במיזם פא"ר)
• שמואל זקס ונסים פרנסיז, ‏אוטומטים ושפות פורמליות ב, האוניברסיטה הפתוחה, 2000 (הספר במיזם פא"ר)

קישורים חיצוניים

מדיה וקבצים בנושא אוטומט מחסנית בוויקישיתוף

• גדי אלכסנדרוביץ', אוטומט מחסנית, באתר "לא מדויק", 22 במרץ 2015

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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