אוטומטים ושפות פורמליות/אוטומט מחסנית

מודל האוטומט הסופי חלש מדי, למשל אינו יכול להכריע שפות כגון $L=\{0^{n}1^{n}\mid n\in \mathbb {N} \}$, שלכאורה מאד פשוטות להכרעה, וניתן לכתוב בקלות תוכנות שמכרעיות שפה כנ"ל.

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

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

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

תיאור סכמטי של אוטומט מחסנית: מימין המחסנית; למטה: סרט הקלט; ובמרכז: מכונת המצבים המתוארת על-ידי הפונקציה $\delta$, והמצב הנוכחי Q.

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

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

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

תיאור פורמלי

קיימים מספר מודלים שקולים לתיאור אוטומט מחסנית.

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

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

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

$\ A=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\dashv ,F)$

כאשר:

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

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

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

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

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

דוגמא

מה מבצע אוטומט המחסנית הבא:

ראשית יש להסביר את הסימון. כל מעבר מסומן בשלושה תווים מהצורה $a,b\to c$ ומשמעותו שאם בסרט הקלט מופיעה האות $a$ ובראש המחסנית האות $b$, אזי האוטומט שולף את האות העליונה במחסנית, כותב במקומה $c$ ומשנה את המצב בהתאם למעבר. אין הכרח לכתוב/לשלוף מהמחסנית אות בכל מעבר: אם לא נכתב דבר למחסנית $c=\epsilon$, ואם לא נקרא (נשלף) דבר מהמחסנית אזי $b=\epsilon$.

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

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

$L=\{ww^{R}\mid w\in \{0,1\}^{*}\}$

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

הפרק הקודם: ביטויים רגולריים

אוטומט מחסנית תרגילים

הפרק הבא: דקדוקים חסרי הקשר