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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
דוגמה לאוטומט מחסנית

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

תיאור לא פורמלי[עריכת קוד מקור | עריכה]

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

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

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

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

תיאור פורמלי[עריכת קוד מקור | עריכה]

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

\ A=\left\{Q,\Sigma,\Gamma,\delta,q_0,\dashv,F\right\}

כאשר:

  • \ Q היא קבוצת מצבי האוטומט.
  • \ \Sigma הוא א"ב של הקלט.
  • \ \Gamma הוא א"ב של המחסנית.
  • \ \delta :Q\times\left(\Sigma\cup\left\{\varepsilon\right\}\right)\times\Gamma\to \mathrm{P}\left(Q\times\Gamma^*\right) היא פונקציית המעברים.
  • \ q_0 הוא המצב ההתחלתי.
  • \ \dashv היא האות ההתחלתית שבמחסנית.
  • \ F\subseteq Q היא קבוצת המצבים המקבלים.

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

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

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

להלן מספר דוגמאות לפעולת פונקציית המעברים שבכולן האוטומט מתחיל במצב \ 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 מראש המחסנית מבלי שיוסיף שום דבר אחר במקומה (כלומר, הוא מוחק את ראש המחסנית).

תיאור חישוב[עריכת קוד מקור | עריכה]

על מנת לתאר חישובים באמצעות אוטומט מחסנית, נהוג להשתמש בתיאור רגעי. תיאור רגעי הוא שלשה שמכילה את המידע הרלוונטי לחישוב הנוכחי של האוטומט - המצב בו הוא נמצא, הקלט שעוד נותר לו לקרוא, ותוכן המחסנית. בצורה פורמלית, מגדירים תיאור רגעי בתור השלשה \ \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^* כדי לסמן שני תיאורים רגעיים שניתן להגיע מהאחד אל השני במספר כלשהו של צעדים.

הגדרת קבלה[עריכת קוד מקור | עריכה]

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

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

  • \ L_f(M)=\left\{w\in\Sigma^*|\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^*|\exists p\in Q: \left(q_0,w,\dashv\right)\vdash^*\left( p,\varepsilon,\varepsilon\right)\right\}

באופן כללי יכול להיות ש-\ L_f(M)\ne L_e(M), כלומר השפה שאוטומט מזהה על ידי הגעה למצב מקבל שונה מהשפה שהוא מזהה על ידי ריקון המחסנית. עם זאת, קיימת שקילות בין שני אופני הקבלה: אם שפה כלשהי \ L מזוהה על ידי הגעה למצב מקבל בידי אוטומט מחסנית כלשהו, קיים אוטומט מחסנית (לא בהכרח אותו אחד) שמזהה אותה על ידי ריקון המחסנית, ולהפך.

לקריאה נוספת[עריכת קוד מקור | עריכה]