שקילות אוטומט מחסנית ודקדוק חסר הקשר

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

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

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

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

עכשיו, איך ניגשים לבניה שלנו? במבט ראשון זה נראה מפחיד ואין לנו מושג מאיפה להתחיל, כי דקדוק זה משהו שמייצר מילים על ידי כך שהוא משליך הרבה אותיות לפה ולשם ופתאום יש מילה מוגמרת, ולעומת זאת אוטומט עובר סדרתית על אותיות ועושה חישובים וכדומה. אבל בעצם, אם חושבים על זה, כבר ראינו משהו דומה - דקדוק שמסמלץ אוטומט סופי דטרמיניסטי. שם הרעיון היה כזה: משתני הדקדוק היו \( Q \), הטרמינלים היו \( \Sigma \) ולכל מעבר \( \delta\left(q,\sigma\right)=p \) היה לנו את כלל הגזירה \( q\to\sigma p \). כך הדקדוק יצר את המילה “אות אחרי אות” כשהסימן הימני ביותר בתבנית הפסוקית שבמהלך הבניה תמיד תיאר את המצב הנוכחי של האוטומט - בעצם, אם חושבים על זה, זה סוג של תיאור של הקונפיגורציה שלו (רק בלי “מה שנשאר מהקלט”).

אז למה לא לעשות בניה דומה עבור אוטומט מחסנית? הרי ההבדל היחיד הוא שעכשיו יש לנו גם מחסנית. למה לא לתאר את הקונפיגורציה הנוכחית של האוטומט בלי שארית הקלט בתור זוג \( \left(q,\alpha\right) \) כאשר \( \alpha\in\Gamma^{*} \) ולכל מעבר \( \left(p,\beta\right)\in\delta\left(q,\sigma,A\right) \) להוסיף את הגזירה הבאה בדקדוק: \( \left(q,A\alpha\right)\to\sigma\left(p,\beta\alpha\right) \)?

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

עדיין, מה שעשינו הוא התחלה טובה שתוביל אותנו בסופו של דבר אל הבניה שעובדת. בואו ננסה להציע לה תיקון נאיבי ונראה מה יקרה: מכיוון שהבעיה שלנו היא עם כך ש-\( \alpha \) הוא לא חסום באורכו, הנה הצעה: פשוט נפרוט אותו לפרוטות. נוסיף את כל \( \Gamma \) לקבוצת המשתנים של הדקדוק שלנו, ועכשיו תבנית פסוקית אופיינית תיראה, נאמר, כך: \( aabqABB \). התבנית הזו אומרת “עד כה הסימולציה של האוטומט שלנו קראה את \( aab \); עכשיו אנחנו במצב \( q \); תוכן המחסנית הוא \( ABB \)”. זה נראה מאוד מבטיח כי האוטומט פועל רק על פי התו העליון במחסנית, שממילא צמוד ל-\( q \), אז נראה שאפשר לעשות כאן משהו.

למה הבניה הזו נכשלת? כי הדקדוק שלנו צריך להיות חסר הקשר. כאשר אני גוזר את המשתנה \( q \), המשתנה לא יודע מי נמצא מימינו ומשמאלו והגזירה לא תהיה מושפעת מזה. במילים אחרות, אין ל-\( q \) דרך “להכיר” את ה-\( A \) שמימינו. תגידו, אוקיי - בואו נחבר את שניהם מראש לזוג, כלומר התבנית תיראה כך: \( aab\left(q,A\right)BB \). זה טוב ויפה, אבל אחרי ש-\( \left(q,A\right) \) נגזר למשהו, איך אותו משהו יתחבר אל ה-\( B \)-ים שמשמאל?

בקיצור, גם זה לא יעבוד. אני לא יכול שיהיו לי משתנים שהם “מצב לבד” ו”אות מחסנית לבד” - אני חייב שהמשתנים שלי יכללו מידע גם עבור המצב וגם עבור האות במחסנית. איך נעשה את זה? בואו ננסה פשוט לחבר אותם לזוגות ונראה איך זה עובד בדוגמה שלעיל: \( \left(q_{3},B\right) \)\( aab\left(q_{1},A\right)\left(q_{2},B\right) \). כאשר כאן \( q_{1},q_{2},q_{3} \) הם מצבים כלשהם. מה שאני מצפה מ-\( \left(q_{1},A\right) \) לגזור זה את “החלק במילה שעליו האוטומט רץ עד לשלב שבו הוא מגיע למצב \( q_{2} \) ובמחסנית נשארו רק \( BB \)”, ומה שאני מצפה מ-\( \left(q_{2},B\right) \) לגזור זה את “החלק במילה שעליו האוטומט רץ עד לשלב שבו הוא מגיע למצב \( q_{3} \) ובמחסנית נשאר רק \( B \)” ו-\( \left(q_{3},B\right) \) אמור לגזור את “החלק המילה שעליו האוטומט רץ עד שהמחסנית מתרוקנת”. משהו כאן עדיין לא עובד, אבל אני חושב שאנחנו כבר רואים שזה מתחמם ואנחנו מתקרבים לבניה שתעבוד.

הבעיה בבניה הנוכחית היא שהיא עדיין תלוית הקשר במובן מסויים - מה זאת אומרת, אני מצפה מ-\( \left(q_{1},A\right) \) לגזור את החלק במילה שעליו האוטומט רץ עד שהוא מגיע ל-\( q_{2} \) ובמחסנית יש \( BB \)? איך הוא יודע מ-\( q_{2} \) ומ-\( BB \)? כרגע הוא לא. אבל שימו לב - הוא בעצם לא באמת מתעניין ב-\( BB \). אפשר לנסח את זה מחדש: \( \left(q_{1},A\right) \) אמור לגזור את החלק במילה שעליו האוטומט רץ עד שהוא מגיע ל-\( q_{2} \) והמחסנית מגיעה למצב שבו מה שהיה מתחת ל-\( A \) נחשף לראשונה. הקטע הזה עם ה”נחשף לראשונה” נראה לי כמו הדבר הכי מבלבל כאן, אז בואו נפרט קצת: על פי ההגדרה שלו, הדבר הראשון שהאוטומט עושה כשהוא מבצע צעד זה להסיר את \( A \) מהמחסנית. אבל מייד אחר כך הוא דוחף במקום \( A \) מילה \( \beta \) כלשהי. אם \( \beta \) היא המילה הריקה, אז מה שהיה מתחת ל-\( A \) נחשף; אחרת, \( A \) הוחלף על ידי תווים נוספים (אולי יותר מ-1) ומה שהיה קבור מתחת ל-\( A \) נשאר קבור ונצטרך לטפל בכל מה שמעליו לפני שנגיע אליו.

אם כן, לא באמת אכפת לנו מה-\( BB \), אבל כן אכפת לנו מ-\( q_{2} \). אבל כאן אין בעצם בעיה, כי \( q_{2} \) הוא מצב בודד ואפשר לזכור אותו - זו כבר לא סדרה בלתי חסומה של תווים. זה מוביל אותנו אל הרעיון שמאחורי הבניה האמיתית שבה נשתמש: המשתנים שלנו יהיו שלשות \( \left(q,A,p\right) \) כך שהמילים ששלשות כאלו גוזרות הן בדיוק המילים שמאפשרות לאוטומט לעבור מ-\( q \) אל \( p \) כאשר בהתחלה \( A \) בראש המחסנית ובסיום נחשף מה שהיה מתחתיו.

בואו נכתוב את זה בצורה פורמלית. אני רוצה לבנות את הדקדוק בצורה כזו שיתקיים הדבר הבא:

\( \left(q,A,p\right)\Rightarrow^{*}w\iff\left[q,w,A\right]\vdash^{*}\left[p,\varepsilon,\varepsilon\right] \)

כאן צד שמאל הוא גזירה בדקדוק, וצד ימין הוא חישוב של האוטומט. שימו לב לאופן הפשוט שבו כל הסיבוך של “הפעם הראשונה שבה מה שמתחת ל-\( A \) נחשף” מבוטא כאן - אני פשוט מתאר את החישוב כאילו הוא מתחיל ממחסנית שבה אין כלום מתחת ל-\( A \), ובצעד האחרון המחסנית מתרוקנת. לא ייתכן שהמחסנית גם לפני הצעד האחרון כי אז האוטומט היה נתקע. לא קשה להוכיח שאם \( \left[q,w,A\right]\vdash^{*}\left[p,\varepsilon,\varepsilon\right] \) אז גם \( \left[q,w,A\beta\right]\vdash^{*}\left[p,\varepsilon,\beta\right] \) לכל \( \beta \) אפשרי, כך שאנחנו לא מגבילים את הכלליות בכך שאנחנו מדברים רק על מה שקורה שהמחסנית ריקה. מעכשיו, לצורך פשטות, אני אדבר על סדרת מעברים כזו פשוט בתור “מעברים שמרוקנים את \( A \)” למרות שפורמלית זה לא ממש נכון (כי \( A \) יכול לעוף במעבר הראשון אבל מה שמתחתיו לא ייחשף מייד, או ש-\( A \) יישאר למשך הרבה זמן, וכו’).

אם אני אצליח לבנות דקדוק שאלו משתניו, זה מסיים כמעט מייד את ההוכחה - שימו לב כמה צד ימין של השקילות דומה להגדרת הקבלה באמצעות ריקון מחסנית. כדי לסיים את הבניה אני אוסיף לדקדוק משתנה התחלתי \( S \) (חייב להיות משתנה התחלתי וטרם ציינתי כזה) ולכל מצב \( p\in Q \) אוסיף את הגזירה \( S\to\left(q_{0},\bot,p\right) \), וסיימנו: \( w\in L\left(M\right) \) אם ורק אם קיים \( p\in Q \) כך ש-\( \left[q_{0},w,\bot\right]\vdash^{*}\left[p,\varepsilon,\varepsilon\right] \), כלומר אם ורק אם קיים \( p\in Q \) כך ש-\( \left(q_{0},\bot,p\right)\Rightarrow^{*}w \), כלומר אם ורק אם \( S\Rightarrow^{*}w \) (למה? זה דורש טיפה נימוק), כלומר אם ורק אם \( w\in L\left(G\right) \).

אז נשאר רק להבין איך לבנות את הדקדוק כך שהשקילות תתקיים. מה זה אומר “לבנות את הדקדוק”? את המשתנים כבר ציינתי - אלו כל השלשות \( \left(q,A,p\right) \); רק נשאר להציג את כללי הגזירה שלהם. פורמלית, הדקדוק שלי הוא \( G=\left(\left\{ S\right\} \cup Q\times\Gamma\times Q,\Sigma,S,P\right) \) ורק נותר לי לתאר את \( P \).

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

המקרה הראשון הוא מעבר מהצורה \( \left(p,\varepsilon\right)\in\delta\left(q,\sigma,A\right) \). שימו לב מה מעבר כזה עושה: הוא מעביר אותנו מ-\( q \) אל \( p \) תוך שהוא מרוקן את \( A \) מהמחסנית - בדיוק מה שהמשתנה \( \left(q,A,p\right) \) בא לתאר. מכיוון שהמעבר הזה משתמש ב-\( \sigma \) לצורך כך (ייתכן ש-\( \sigma \) היא המילה הריקה), אז אנחנו מקבלים את הגזירה \( \left(q,A,p\right)\to\sigma \).

ועכשיו לסיטואציה המסובכת - מעבר מהצורה \( \left(p,B_{1}B_{2}\dots B_{n}\right)\in\delta\left(q,\sigma,A\right) \). כאן \( A \) הוחלף על ידי \( B_{1}\dots B_{n} \) ולכן כדי להשיג את האפקט של ריקון \( A \) מהמחסנית, אנחנו צריכים לרוקן את \( B_{1},\dots,B_{n} \). זה מזמין את הגזירה הבאה:

\( \left(q,A,q_{n+1}\right)\to\sigma\left(q_{1},B_{1},q_{2}\right)\left(q_{2},B_{2},q_{3}\right)\cdots\left(q_{n},B_{n},q_{n+1}\right) \)

שמתארת את הסיפור הבא: קודם כל עברנו מ-\( q \) אל \( q_{1} \) תוך קריאת \( \sigma \) והחלפת \( A \) ב-\( B_{1}\cdots B_{n} \); אחר כך נעבור מ-\( q_{1} \) אל \( q_{2} \) ונרוקן את \( B_{1} \) תוך כדי; מ-\( q_{2} \) נעבור אל \( q_{3} \) תוך ריקון \( B_{2} \) וכן הלאה, עד אשר נעבור מ-\( q_{n} \) אל \( q_{n+1} \) תוך ריקון \( B_{n} \).

הכל טוב ויפה חוץ מדבר אחד - מי לכל הרוחות הם המצבים \( q_{1},q_{2},\dots,q_{n+1} \)? מאיפה הם באו? כל מי שהיו לי במעבר המקורי באוטומט היו \( q,p \), ולאן \( p \) נעלם באמת?

אז בבירור \( q_{1}=p \), אבל זה עדיין לא מסביר מיהם המצבים \( q_{2},\dots,q_{n+1} \). התשובה היא שאני לא יודע. המטרה של הגזירה של \( \left(q,A,q_{n+1}\right) \) היא לתאר את כל הריצות האפשריות שבהן יסירו את \( B_{1}\cdots B_{n} \) מהמחסנית, ואני לא יודע מה מצבי הביניים בהן יהיו. אז מה שאני עושה הוא לכסות את כל האפשרויות. כלומר, אני הולך להוסיף את הגזירה

\( \left(q,A,q_{n+1}\right)\to\sigma\left(q_{1},B_{1},q_{2}\right)\left(q_{2},B_{2},q_{3}\right)\cdots\left(q_{n},B_{n},q_{n+1}\right) \)

עבור כל בחירת ערכים אפשרית ל-\( q_{2},\dots,q_{n+1} \). ומה קורה אם, למשל, אין דרך להגיע מ-\( q_{1} \) אל \( q_{2} \) תוך הסרת \( B_{1} \) עבור בחירה מסויימת של \( q_{2} \)? אין בעיה. אז הגזירה הזו “תיתקע” כי המשתנה \( \left(q_{1},B_{1},q_{2}\right) \) לא יצליח לגזור מילה טרמינלית. לא נורא - אני לא חייב שכל נסיון גזירה יצליח.

קרוב לודאי שחלק מכם תוהים עכשיו למה טרחתי לפצל את כללי הגזירה לשניים, כשבעצם יש לי רק כלל גזירה אחד בשני המקרים - ה”פשוט” וה”מסובך”: הכלל \( \left(q,A,q_{n+1}\right)\to\sigma\left(q_{1},B_{1},q_{2}\right)\left(q_{2},B_{2},q_{3}\right)\cdots\left(q_{n},B_{n},q_{n+1}\right) \) עם האילוץ ש-\( p=q_{1} \). המקרה ה”פשוט” מתקבל כאשר \( n=0 \). ובכן, אפשר לעשות את זה כך, אבל לדעתי זה פשוט מבלבל יותר ואני לא רואה בזה טעם. כדאי להזכיר למי ששכח או לא יודע שהרעיון במתמטיקה הוא להיות ברור; לא להיות מינימליסטי. מינימליזם הוא טוב אם הוא מפשט עניינים, אבל אני לא חושב שהוא מטרה בפני עצמה.

בואו נעבור עכשיו להוכחה חצי פורמלית לכך שהבניה עובדת. אני חושב שכאן מאוד מועיל לראות הוכחה כזו כי למרות שאני מקווה שכבר יש לנו אינטואיציה לא רעה לגבי מה הבניה הזו ומאיפה היא הגיעה, עדיין חסר משהו כדי להשתכנע שזה אכן עובד. כזכור, כל מה שנשאר לי להוכיח הוא את הטענה \( \left(q,A,p\right)\Rightarrow^{*}w\iff\left[q,w,A\right]\vdash^{*}\left[p,\varepsilon,\varepsilon\right] \). זו טענת אם-ורק-אם כך שאני צריך להוכיח שני כיוונים. נטפל בכל אחד מהם בנפרד.

נתחיל מכך שנתון \( \left(q,A,p\right)\Rightarrow^{*}w \) ונוכיח ש-\( \left[q,w,A\right]\vdash^{*}\left[p,\varepsilon,\varepsilon\right] \). כלומר, אם המשתנה \( \left(q,A,p\right) \) גוזר מילה כלשהי, אז המילה הזו מעבירה את האוטומט מ-\( q \) אל \( p \) תוך סילוק \( A \) מהמחסנית. נוכיח את זה באינדוקציה, וזו הזדמנות טובה לשאול את עצמנו - אינדוקציה על מה? כלל האצבע הוא זה - נסתכל על האובייקט שאת קיומו אנחנו מניחים וממנו אנחנו רוצים להסיק דברים, ונבצע אינדוקציה על מאפיין כלשהו שלו שהולך ונעשה מורכב יותר. כאן האובייקט הנתון הוא הגזירה של \( w \) מתוך המשתנה; הפרמטר יהיה אורך הגזירה. הבסיס הוא גזירה בת צעד אחד, וזה קל - בגזירה בת צעד אחד שגוזרת מילה טרמינלית ממשתנה, צעד הגזירה חייב להיות כזה שלא יוצר משתנים אלא רק טרמינלים, כלומר הוא חייב להיות גזירה מהצורה ה”פשוטה”, \( \left(q,A,p\right)\to\sigma \). מכאן אנחנו לומדים שני דברים: ש-\( w=\sigma \), וש-\( \left(p,\varepsilon\right)\in\delta\left(q,\sigma,A\right) \). מסקנה: \( \left[q,w,A\right]=\left[q,\sigma,A\right]\vdash\left[p,\varepsilon,\varepsilon\right] \).

נעבור אל צעד האינדוקציה. כאן אנחנו מניחים שהטענה נכונה לכל גזירה מאורך קטן מ-\( k \) (עבור \( k\ge2 \)) ומוכיחים עבור \( \left(q,A,p\right)\Rightarrow^{k}w \). התעלול הוא לרוב לפרק את הגזירה לצעד ראשון או אחרון, ו”כל היתר” שעליהם אפשר להפעיל את הנחת האינדוקציה. כאן יהיה לנו נוח לפרק לפי הצעד הראשון, שחייב להיות גזירה מהצורה ה”מסובכת”, כי אחרת נקבל מילה טרמינלית אחרי הצעד הראשון ולכן לא ייתכן שהגזירה היא בת שני צעדים או יותר.

כלומר, מתקיים \( \left(q,A,p\right)\Rightarrow\sigma\left(p,B_{1},q_{2}\right)\left(q_{2},B_{2},q_{3}\right)\cdots\left(q_{n},B_{n},q_{n+1}\right)\Rightarrow^{*}w \) וזה נובע מכך שבאוטומט קיים המעבר \( \left(p,B_{1}B_{2}\dots B_{n}\right)\in\delta\left(q,\sigma,A\right) \). בגזירה שמתוארת כאן, כל אחד מהמשתנים מתישהו נגזר לגמרי למילה טרמינלית כלשהי; בואו נסמן אותן באופן הבא: \( \left(q_{i},B_{i},q_{i+1}\right)\Rightarrow^{*}w_{i} \). המסקנה היא ש-\( w=\sigma w_{1}\cdots w_{n} \), ושניתן להפעיל את הנחת האינדוקציה על כל גזירה מהצורה \( \left(q_{i},B_{i},q_{i+1}\right)\Rightarrow^{*}w_{i} \) (כי הן בנות פחות מ-\( k \) צעדים) ולקבל \( \left[q_{i},w_{i},B\right]\vdash^{*}\left[q_{i+1},\varepsilon,\varepsilon\right] \).

עכשיו נחבר את כל אלו כדי לקבל הוכחה לכך ש-\( \left[q,w,A\right]\vdash^{*}\left[p,\varepsilon,\varepsilon\right] \):

\( \left[q,w,A\right]=\left[q,\sigma w_{1}\cdots w_{n},A\right]\vdash\left[p,w_{1}\cdots w_{n},B_{1}\dots B_{n}\right]\vdash^{*} \)

\( \vdash^{*}\left[q_{2},w_{2}\cdots w_{n},B_{2}\cdots B_{n}\right]\vdash^{*}\left[q_{n},w_{n},B_{n}\right]\vdash^{*}\left[q_{n+1},\varepsilon,\varepsilon\right] \)

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

הכיוון השני דומה באופיו אבל אני אנפנף בו קצת יותר בידיים. הפעם נתון לי \( \left[q,w,A\right]\vdash^{*}\left[p,\varepsilon,\varepsilon\right] \) ואני רוצה להוכיח ש-\( \left(q,A,p\right)\Rightarrow^{*}w \) - ושוב, אעשה זאת באינדוקציה, הפעם על אורך החישוב באוטומט. אם החישוב הוא בן צעד בודד, אז הצעד הזה חייב להיות מהצורה \( \left(p,\varepsilon\right)\in\delta\left(q,\sigma,A\right) \) (אחרת לא היה אפשר לרוקן את \( A \) מהמחסנית) ו-\( w=\sigma \). מסקנה: בדקדוק שבנינו קיים הכלל \( \left(q,A,p\right)\rightarrow\sigma \) וקיבלנו ש-\( \left(q,A,p\right)\Rightarrow^{*}\sigma=w \). יופי, זה היה קל.

עכשיו לצעד: נניח שהטענה נכונה לכל חישוב מאורך קטן מ-\( k \). ונוכיח עבור חישוב באורך \( k \) כאשר \( k\ge2 \). אם \( \left[q,w,A\right]\vdash^{k}\left[p,\varepsilon,\varepsilon\right] \) אז נוח לפרק על פי הצעד הראשון, שחייב להיות כזה שלא מרוקן את המחסנית (אחרת לא היה אחריו עוד צעד). כלומר, הצעד הראשון משתמש במעבר מהצורה \( \left(q_{1},B_{1}B_{2}\dots B_{n}\right)\in\delta\left(q,\sigma,A\right) \), ולכן החישוב מתחיל כך: \( \left[q,w,A\right]\vdash\left[q_{1},w^{\prime},B_{1}\cdots B_{n}\right] \), כאשר \( w=\sigma w^{\prime} \). כאן מגיע נפנוף הידיים.

מה שאני אומר הוא זה: אני יודע שמהקונפיגורציה \( \left[q_{1},w^{\prime},B_{1}\cdots B_{n}\right] \) החישוב נמשך עד שהוא מסתיים בקונפיגורציה \( \left[p,\varepsilon,\varepsilon\right] \). בפרט, המחסנית ריקה בסוף וסיימנו לקרוא את כל \( w^{\prime} \). מכיוון שהמחסנית ריקה, היה חייב להיות רגע שבו \( B_{2} \) נחשף לראשונה (כלומר, בניסוח הלא פורמלי שהשתמשתי בו עד כה, רגע שבו “\( B_{1} \) מוסר מהמחסנית”). וכמו כן חייב להיות רגע שבו \( B_{3} \) נחשף, וכן הלאה, עד הרגע האחרון, שבו המחסנית מתרוקנת.

אם כן, אני אפרק את \( w^{\prime} \) בהתאם לרגעים הללו: \( w_{1} \) הוא כל מה שהאוטומט קרא עד לרגע שבו \( B_{2} \) נחשף, ו-\( w_{2} \) הוא כל מה שהאוטומט קרא עד לרגע שבו \( B_{3} \) נחשף, וכן הלאה. כמו כן, אני אקרא בשם \( q_{2} \) למצב שאליו מגיעים בדיוק כש-\( B_{2} \) נחשף, וכן הלאה. שימו לב לכך ש-\( w^{\prime}=w_{1}\cdots w_{n} \).

אם כן, הסימונים שנתתי מתארים את הסיטואציה הבאה: \( \left[q_{i},w_{i}w_{i+1}\cdots w_{n},B_{i}B_{i+1}\cdots B_{n}\right]\vdash^{*}\left[q_{i+1},w_{i+1}\cdots w_{n},B_{i+1}\cdots B_{n}\right] \). כעת לנפנוף הידיים האחרון: מכיוון שבחישוב הזה אין ל-\( w_{i+1}\cdots w_{n} \) שום השפעה (כי עוד לא הגענו לחלק הזה בקלט) וכמו כן גם ל-\( B_{i+1}\cdots B_{n} \) אין שום השפעה (כי האוטומט לא רואה אותם בשום שלב של החישוב - כאן קריטית לגמרי העובדה שאני מסיים את החלק הזה של החישוב בדיוק כאשר \( B_{i+1} \) נחשף לראשונה), הרי שאפשר פשוט להתעלם מהם - כלומר, מתקיים \( \left[q_{i},w_{i},B_{i}\right]\vdash^{*}\left[q_{i+1},\varepsilon,\varepsilon\right] \). וזה מצויין עבורי, כי על הדבר הזה אפשר להשתמש בהנחת האינדוקציה - הוא מהצורה המתאימה (אני מסיים בקונפיגורציה שבה הקלט שנותר והמחסנית שניהם ריקים) והוא מתאר חישוב באורך קטן מ-\( k \) (כי הוא חלק מחישוב באורך \( k \) בלי הצעד הראשון של אותו חישוב). קיבלנו ש-\( \left(q_{i},B_{i},q_{i+1}\right)\Rightarrow^{*}w_{i} \) לכל \( 1\le i\le n \).

כעת אפשר לסיים על ידי הצגת גזירה של \( w \):

\( \left(q,A,p\right)\Rightarrow\sigma\left(q_{1},B_{1},q_{2}\right)\cdots\left(q_{n},B_{n},q_{n+1}\right)\Rightarrow^{*}\sigma w_{1}w_{2}\cdots w_{n}=\sigma w^{\prime}=w \)

וזה מסיים את הכיוון השני של ההוכחה, ואת ההוכחה כולה.

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