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

בפוסטים הקודמים על שפות פורמליות הגדרתי את המושג של שפה חסרת הקשר. שפה היא חסרת הקשר אם יוצר אותה דקדוק חסר הקשר. זה מייצג גישה שונה לשפות פורמליות ביחס לזו שבה נקטתי עבור שפות רגולריות - שם הגדרתי את המחלקה לא באמצעות דקדוק שמייצר אותה (למרות שאפשר, והראיתי מחלקת דקדוקים כזו - דקדוקים לינאריים ימניים), אלא באמצעות מודל של אוטומט שמסוגל לזהות שפות. מה זה אומר “לזהות” שפה \( L \)? שהאוטומט, בהינתן קלט \( w \), רץ על הקלט ובסוף אומר “כן” אם \( w\in L \) ו”לא” אם \( w\notin L \).

התהיה הטבעית שלנו היא האם קיים מודל דומה של אוטומט, או מכונה חישובית דומה, שתופס בדיוק את מחלקת השפות חסרות ההקשר. המודל של אוטומט סופי דטרמיניסטי הוא חלש מדי - את השפה חסרת ההקשר \( L=\left\{ a^{n}b^{n}\ |\ n\in\mathbb{N}\right\} \) אין אוטומט סופי דטרמיניסטי שמזהה. לעומת זאת, המודל החישובי הסטנדרטי של מדעי המחשב - מכונת טיורינג - הוא חזק מדי; הוא מזהה את השפה \( L=\left\{ a^{n}b^{n}c^{n}\ |\ n\in\mathbb{N}\right\} \) שאוכיח בעתיד שאינה חסרת הקשר. אם כן, אנחנו מחפשים מודל “ביניים” כלשהו בין אוטומט סופי דטרמיניסטי ובין מכונת טיורינג.

מה בעצם ההבדל בין שני המודלים הללו? הרעיון מאחורי אוטומט סופי דטרמיניסטי הוא זכרון קבוע, כלומר שימוש בכמות זכרון שאינה תלויה בכלל בגודל הקלט. לעומת זאת, למכונת טיורינג יש זכרון לא חסום. לכן נראה מתבקש שהגבלה כלשהי על כמות הזכרון תניב לנו את מחלקת השפות חסרות ההקשר. למשל - אפשר לדרוש שכמות הזכרון שבה משתמשים לא תעלה על אורך הקלט. במילים אחרות, בזמן שאוטומט סופי דטרמיניסטי עובר על הקלט משמאל לימין ויכול רק לקרוא אותו, אפשר לחשוב על הרחבה של המודל שבה מותר לאוטומט ללכת ימינה ושמאלה בחופשיות על הקלט (למעשה, זה בפני עצמו לא מגדיל את הכוח של המודל ואוכיח זאת בפוסט עתידי), וגם מותר לו לכתוב על תאי הקלט, כלומר למחוק את מה שהיה שם קודם ולשים משהו חדש במקום. מודל כזה אכן מגדיר מחלקת שפות מעניינת, אבל זו אינה מחלקת השפות חסרות ההקשר אלא דווקא מחלקה אחרת של שפות שאפשר לתאר בעזרת דקדוקים שנקראת מחלקת השפות תלויות ההקשר. גם זה נושא יפה לפוסט עתידי ולא ארחיב על כך כעת; בינתיים רק חשבו על האופן שבו תכריעו את \( \left\{ a^{n}b^{n}c^{n}\ |\ n\in\mathbb{N}\right\} \) בעזרת אוטומט שכזה (רמז: זה ממש, ממש קל).

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

אם כן, נתון לי דקדוק \( G=\left(V,T,S,P\right) \) ונתונה לי מילה \( w\in T^{*} \). אני תוהה האם קיימת דרך לייצר את המילה הזו מתוך \( G \). איך אני עושה את זה? הנה הצעה מאוד נאיבית: בואו פשוט ננסה גזירה כלשהי בדקדוק ונראה אם נקבל בסופו של דבר את \( w \). כלומר, נתחיל עם \( S \), נבחר באופן שרירותי כלל גזירה \( S\to\alpha \) מבין כל כללי הגזירה שמערבים את \( S \) ונחליף את \( S \) ב-\( \alpha \); אחר כך, כל עוד יש משתנה ב-\( \alpha \) נבחר כלל גזירה עבורו ונשכתב את \( \alpha \) וכן הלאה, עד אשר נקבל מחרוזת שכולה טרמינלים. ואז נשווה אותה ל-\( w \).

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

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

בכל שלב של ריצת האלגוריתם אנחנו מחזיקים ביד תבנית פסוקית \( \alpha \) (מילה ב-\( \left(V\cup T\right)^{*} \)). בגישה הנאיבית אני מחפש משתנה בתבנית הזו וגוזר אותו. בגישה הקצת פחות נאיבית, אני מציע להסתכל על התו הראשון ב-\( \alpha \). אם הוא משתנה, אגזור אותו; אם הוא טרמינל, אשווה אותו לטרמינל במקום המתאים ב-\( w \), ואם הם שונים אדחה מייד. אם הם זהים, אעיף את הטרמינל מ-\( \alpha \) ואעבור למקום הבא ב-\( w \). זה הכל.

הנה תיאור פורמלי של האלגוריתם. בכל צעד אני מחזיק שתי מילים: \( u\in T^{*} \) ו-\( \alpha\in\left(V\cup T\right)^{*} \). בתחילת ריצת האלגוריתם \( u=w \) (הקלט שלי) ו-\( \alpha=S \).

בכל צעד של האלגוריתם, אני מסתכל על התו הראשון ב-\( \alpha \). אם התו הראשון הזה הוא טרמינל, כלומר \( \alpha=a\alpha^{\prime} \) כך ש-\( a\in T \), אני בודק אם \( u=au^{\prime} \). אם לא, אני עוצר ודוחה מייד; אם כן, אני מוחק את \( a \) הן מ-\( \alpha \) והן מ-\( u \). כלומר, אני מבצע את ההשמות \( \alpha\leftarrow\alpha^{\prime} \) ו-\( u\leftarrow u^{\prime} \). אני אקרא לפעולה הזו Shift בהמשך כי אני “מזיז” את הקלט.

אם התו הראשון ב-\( \alpha \) היה משתנה, כלומר \( \alpha=A\alpha^{\prime} \), אני בוחר באופן שרירותי כלל גזירה \( A\to\beta\in P \) ומבצע את ההשמה \( \alpha\leftarrow\beta\alpha^{\prime} \).

אם בשלב כלשהו הגעתי בו זמנית לכך ש-\( \alpha=u=\varepsilon \), אני עוצר ומקבל. אם אחת מהמילים הללו התרוקנה מבלי שהשניה תתרוקן, אני דוחה. זה הכל.

האלגוריתם הזה נמצא בשימוש אמיתי בקומפיילרים וכלים דומים לניתוח תחבירי - זו דוגמה לאלגוריתם פרסור שהוא Top Down. רק שבעולם האמיתי אין לאלגוריתמים את הפריבילגיה של להיות אי דטרמיניסטיים ולכן עיקר החוכמה שלהם היא בבחירה של איזה כללי גזירה להפעיל בכל שלב (לרוב על ידי “הצצה קדימה” ב-\( u \)). זה אומר שהאלגוריתמים הללו מסובכים קצת יותר ממה שהצגתי, ושהם לא עובדים לכל הדקדוקים. לא אכנס לכך כרגע. תחת זאת, אני רוצה לתהות איזה מודל חישובי מתאים לאלגוריתם שאני תיארתי.

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

אם כן, מדוע אני לא יכול לבצע את האלגוריתם הזה באוטומט סופי? כי אני צריך לאחסן את \( \alpha \) היכן שהוא, ואין לי שום חסם על הגודל של \( \alpha \). לא חסם של \( O\left(1\right) \) זכרון, ולא חסם של \( O\left(\log n\right) \) ולא חסם של \( O\left(n\right) \) ולא כלום. אם אתם לא משוכנעים, נסו להמציא לי דקדוק שבו מילים יכולות להגיע לאורך שרירותי לפני שמתחילים לגזור מהן את הטרמינלים - זה תרגיל נחמד. אם כן, כל הכיוון שחשבתי עליו בהתחלה, של “בואו נגביל את כמות הזכרון של המודל” לא רלוונטית פה בכלל. אז מה הרווחתי? הרי אם כמות הזכרון אינה חסומה, אנחנו מקבלים מכונת טיורינג כללית!

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

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

אין לי הגדרה מדויקת למהו “מבנה נתונים” אבל הרעיון הכללי הוא זה: מבנה נתונים באופן כללי מאפשר לנו לעשות שלושה דברים: להכניס לתוכו פריטי מידע, להוציא מתוכו את פריטי המידע הללו, ולגשת אל פריטי המידע. מבני נתונים שונים נבדלים באופן שבו מתבצעות הפעולות הללו, ביעילות הביצוע שלהן, בכמות הזכרון שנדרשת לייצוג מבנה הנתונים מעבר להחזקת פריטי המידע, וכן הלאה. מחסנית היא מבנה נתונים פשוט מאוד, שאפשר לתאר את פעולתו עם הקיצור LIFO, מלשון Last-in-first-out - האחרון להיכנס הוא הראשון לצאת. פעולת ההכנסה לתוך מחסנית נקראת Push, פעולת ההוצאה נקראת Pop, ולרוב הגישה שלנו היא רק אל האיבר האחרון שנדחף למחסנית, ומכונה Top. הסיבה שקוראים בעברית למבנה הנתונים הזה “מחסנית” היא כי כך מתנהגת מחסנית של כלי נשק - הקליעים נדחפים אליה בצורה כזו שהקליע האחרון שנדחף פנימה יהיה הראשון שיצא החוצה. למי שההקשר המיליטריסטי הזה לא נעים לו, באנגלית קוראים למבנה הנתונים הזה Stack ואפשר לחשוב עליו, למשל, בתור ערימת צלחות - אם אתם צריכים צלחת, אתם תיקחו את זה שבראש הערימה, ולא תיגשו למה שנמצא באמצע.

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

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

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

עד כאן על המוטיבציה. אבל עכשיו נשאלת השאלה - איך אני מגדיר פורמלית את המודל שלי?

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

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

אז הנה הפורמליזציה. אוטומט מחסנית הוא שביעייה \( M=\left(Q,\Sigma,\Gamma,q_{0},\bot,\delta,F\right) \) כך ש-\( Q \) היא קבוצה סופית של מצבים, \( \Sigma \) הוא א”ב הקלט, \( \Gamma \) הוא א”ב אחר שנקרא א”ב המחסנית, \( q_{0}\in Q \) הוא המצב ההתחלתי של האוטומט, \( F\subseteq Q \) היא קבוצת המצבים המקבלים שלו, \( \bot\in\Gamma \) הוא סימן תחתית המחסנית, ופונקציית המעברים… זה מסובך.

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

\( \delta:Q\times\left(\Sigma\cup\left\{ \varepsilon\right\} \right)\times\Gamma\to2^{Q\times\Gamma^{*}} \) עם הדרישה הנוספת ש-\( \left|\delta\left(q,\sigma,A\right)\right|<\infty \) לכל \( q\in Q,\sigma\in\Sigma\cup\left\{ \varepsilon\right\} ,A\in\Gamma \).

איך מתארים חישוב שמבצעת מכונה כזו? באוטומט השתמשנו בטריק של “הרחבת פונקציית המעברים” אבל כאן זה כבר יצא מסורבל מדי. תחת זאת, אנחנו משתמשים בשיטה שקצת מזכירה את האופן שבו אנחנו מתארים “חישובים” של דקדוקים - סדרה של “מצבי ביניים” כך שממצב ביניים אחד לבא אחריו מגיעים על ידי צעד בודד של המכונה. “מצב ביניים” כזה, או כפי שאקרא לו, קונפיגורציה, כולל את כל המידע הרלוונטי על מצב המכונה - במקרה שלנו זה כולל שלושה פרטי מידע: את המצב הפנימי של המכונה, את מה שנשאר מהקלט שלה (קלט שכבר קראנו לא מעניין אותנו יותר) ואת תוכן המחסנית (לא רק את התו העליון בה - כל התוכן, כי גם אם רק התו העליון רלוונטי כרגע, שאר התוכן עשוי להיות רלוונטי בהמשך). אני אסמן קונפיגורציה באופן הבא: \( \left[q,w,\alpha\right] \) כך ש-\( w\in\Sigma^{*} \) ו-\( \alpha\in\Gamma^{*} \).

למכונה יש קונפיגורציה התחלתית יחידה ברורה: \( \left[q_{0},w,\bot\right] \), כך ש-\( w \) היא מילת הקלט שלה. עכשיו אני רוצה להגדיר יחס של “עוקב” עבור קונפיגורציות. אז בואו ניקח מעבר כללי כלשהו של האוטומט, \( \left(p,\beta\right)\in\delta\left(q,\sigma,A\right) \), ובואו ניקח קונפיגורציה כלשהי שבה המעבר הזה יכול להתבצע - דהיינו, האוטומט במצב \( q \), אות הקלט הבאה שהוא יקרא היא \( \sigma \) (או, אם \( \sigma=\varepsilon \), זה לא חשוב מה הקלט), והתו בראש המחסנית הוא \( A \). כל קונפיגורציה כזו היא מהצורה \( \left[q,\sigma w,A\alpha\right] \) (שימו לב איך אני כותב את תוכן המחסנית - משמאל לימין, כאשר התו השמאלי ביותר הוא העליון ביותר והימני ביותר הוא התחתון ביותר). המעבר מגדיר את ה”עוקב” הבא:

\( \left[q,\sigma w,A\alpha\right]\vdash\left[p,w,\beta\alpha\right] \)

שימו לב שמההגדרה הזו נובע מייד שאם בקונפיגורציה כלשהי המחסנית ריקה, לא תהיה לקונפיגורציה הזו קונפיגורציה עוקבת - המכונה “נתקעת”. מצד שני, אם הקלט נגמר, עדיין יכולות להיות אינספור קונפיגורציות עוקבות, שמתאימות למעברי \( \varepsilon \). עכשיו, בואו ניקח את הסגור הרפלקסיבי-טרנזיטיבי של \( \vdash \) ונסמן אותו ב-\( \vdash^{*} \) וקיבלנו יחס שאומר “אפשר להגיע לקונפיגורציה הזו מהקונפיגורציה הזו במספר סופי כלשהו של צעדים”.

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

\( w\in L\left(M\right)\iff\exists p\in F,\alpha\in\Gamma^{*}:\left[q_{0},w,\bot\right]\vdash^{*}\left[p,\varepsilon,\alpha\right] \)

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

\( L_{e}\left(M\right)=\left\{ w\in\Sigma^{*}\ |\ \exists p\in Q:\left[q_{0},w,\bot\right]\vdash^{*}\left[p,\varepsilon,\varepsilon\right]\right\} \)

לשפה \( L_{e}\left(M\right) \) קוראים “השפה שהאוטומט מקבל על ידי ריקון מחסנית”. מכיוון שלפעמים עדיין יותר נוח לעבוד עם מצבים מקבלים, לא מוותרים גם על ההגדרה הקודמת, ומגדירים גם את ה”השפה שהאוטומט מקבל על ידי מצבים מקבלים”:

\( L_{f}\left(M\right)=\left\{ w\in\Sigma^{*}\ |\ \exists p\in F,\alpha\in\Gamma^{*}:\left[q_{0},w,\bot\right]\vdash^{*}\left[p,\varepsilon,\alpha\right]\right\} \)

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

בואו נראה דוגמה פשוטה - אוטומט שמקבל את\( L=\left\{ a^{n}b^{n}\ |\ n\in\mathbb{N}\right\} \) על ידי ריקון. הרעיון: בהתחלה האוטומט בהלך רוח של “לקרוא \( a \)-ים” - לכל \( a \) שהוא קורא הוא דוחף \( A \) למחסנית (בהתחלה במקום סימן תחתית המחסנית, ואחר כך מעל ל-\( A \) הקודם שהוא דחף). אם הוא קורא \( b \) בשלב כזה הוא פשוט נתקע. מתישהו הוא מחליט אי דטרמיניסטית שנמאס לו ועובר בעזרת מסע \( \varepsilon \)להלך רוח של “לקרוא \( b \)-ים”. מעכשיו אם הוא קורא \( a \) הוא נתקע, ואם הוא קורא \( b \) הוא מוציא \( A \) מהמחסנית. כך זה נמשך עד שהמחסנית מתרוקנת. אם היא התרוקנה בו זמנית עם סיום הקלט, מה טוב - אכן אמורים לקבל; אחרת, נתקעים. ואם המילה נגמרה כשהמחסנית לא ריקה, הרי שלא קיבלנו אותה.

הנה האוטומט:

\( \delta\left(q_{0},a,\bot\right)=\left\{ \left(q_{0},A\right)\right\} \)

\( \delta\left(q_{0},a,A\right)=\left\{ \left(q_{0},AA\right)\right\} \)

\( \delta\left(q_{0},\varepsilon,A\right)=\left\{ \left(q_{1},A\right)\right\} \)

\( \delta\left(q_{1},b,A\right)=\left\{ \left(q_{1},\varepsilon\right)\right\} \)

מה שמעניין בעיקר כאן הוא השינויים שאנחנו מבצעים במחסנית, כי בהתחלה קשה לעכל את הפורמליזציה הזו. בשורה הראשונה אנחנו מחליפים את \( \bot \) ב-\( A \). בשניה אנחנו דוחפים \( A \) אחד מעל הנוכחי - או, פורמלית, אנחנו מוציאים \( A \) ודוחפים \( AA \) במקומו. בשלישית אנחנו לא משנים את המחסנית - או, פורמלית, מוציאים \( A \) ואז דוחפים \( A \). בשורה הרביעי אנחנו מוציאים את \( A \) ולא דוחפים שום דבר במקומו.

עכשיו אחרי שהבנו פחות או יותר מה הולך כאן, אפשר לחזור ליעד המקורי שלנו סוף כל סוף - לתאר אוטומט מחסנית שמזהה (על ידי ריקון מחסנית) את השפה של דקדוק חסר הקשר כלשהו. הבניה קלה למדי - כבר הבנו את הרעיון שלה (אני מקווה) ורק נשאר להבין את הפורמליזם. ניקח דקדוק \( G=\left(V,T,S,P\right) \) ונגדיר אוטומט \( M=\left(\left\{ q_{0}\right\} ,T,V\cup T,q_{0},S,\delta,\emptyset\right) \). כלומר: לאוטומט יהיה רק מצב אחד, לא יהיו לו מצבים מקבלים בכלל, וא”ב המחסנית כולל את כל סימני הדקדוק. סימן תחתית המחסנית יהיה \( S \) - המשתנה ההתחלתי (מתאים בדיוק לאלגוריתם שתיארתי קודם).

והצעדים? בדיוק שניים, אחד עבור המקרה של טרמינל בראש המחסנית שזהה לאות הבאה בקלט, ואחד עבור המקרה של משתנה בראש המחסנית:

לכל \( a\in T \): \( \delta\left(q_{0},a,a\right)=\left\{ \left(q_{0},\varepsilon\right)\right\} \)

לכל \( A\in V \):\( \delta\left(q_{0},\varepsilon,A\right)=\left\{ \left(q_{0},\alpha\right)\ |\ A\to\alpha\in P\right\} \)

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

לאלו מכם שאוהבים לאפטמז, אפשר לתת בניה קצרה אפילו עוד יותר, אם מניחים שהדקדוק נמצא בצורה נורמלית מסויימת שנקראת הצורה הנורמלית של גרייבך. אציג אותה במפורט בהמשך, אבל הרעיון הכללי הוא שדקדוק הוא בצורה הנורמלית הזו אם כל כלל גזירה שלו הוא מהצורה \( A\to aA_{1}A_{2}\dots A_{n} \) עבור \( a\in T \) ו-\( A_{1},\dots,A_{n}\in V \) או \( A\to\varepsilon \). כלומר, כל גזירה שלא סתם מוחקת את המשתנה גוזרת בדיוק טרמינל אחד ואז עוד כמה משתנים (זה בעצם כמו דקדוק לינארי ימני, אבל כאן מותר לגזור יותר ממשתנה אחד בפעם). לא קשה להוכיח שלכל שפה חסרת הקשר יש דקדוק בצורה הנורמלית של גרייבך, כך שאנחנו לא מאבדים את הכלליות. כעת, הבניה שלנו תהיה כזו:

לכל \( a\in T \) ולכל גזירה \( A\to aA_{1}\dots A_{n} \) נוסיף את המעבר \( \left(q_{0},A_{1}\dots A_{n}\right)\in\delta\left(q_{0},a,A\right) \). כמו כן אם \( A\to\varepsilon \) נוסיף את המעבר \( \left(q_{0},\varepsilon\right)\in\delta\left(q_{0},\varepsilon,A\right) \). בבניה הזו א”ב המחסנית כולל רק את \( V \), וההוכחה שזה עובד היא פשוטה משמעותית יותר.

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