שפות חסרות הקשר - תכונות סגור

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

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

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

אוטוטו נראה שאיחוד הוא כן תכונת סגור, ולכן מכך שחיתוך אינו תכונת סגור אנחנו לומדים גם שמשלים אינו יכול להיות תכונת סגור (כי אפשר לקבל חיתוך בעזרת משלים ואיחוד - כללי דה-מורגן). לכן אפשר להשתמש גם במשלים כדי לקבל אינטואיציה, אולי אפילו חזקה יותר (למשל, עבור מכונות טיורינג אי דטרמיניסטיות דווקא כן יש סגירות לחיתוך, אבל אין סגירות למשלים - בלשון פורמלית, \( \mbox{RE}\ne\mbox{coRE} \)). הבעיה במשלים היא דווקא לא בצורך שלנו לדחות מילים שהיו שייכות לשפה שאנחנו משלימים - את זה קל לעשות - הקושי הוא בלקבל דווקא את המילים שקודם לא היו בשפה (ולכן בדקדוק אין שום דבר שמייצר אותן, ובאוטומט מחסנית אין להן אף מסלול מקבל, אבל הרי גם למילים בשפה יכולים להיות מסלולים דוחים רבים אז סתם להחליף בין המצב המקבל והדוחה לא יעבוד).

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

שלוש הפעולות החביבות עלינו בשפות רגולריות היו איחוד, שרשור וסגור קלייני שכן משפט קלייני הראה שבעזרתן אפשר לבנות את כל השפות הרגולריות מתוך כל השפות הסופיות. נניח שיש לנו שתי שפות חסרות הקשר \( L_{1},L_{2} \) עם דקדוקים שמייצרים אותן \( G_{1}=\left(V_{1},T,S_{1},P_{1}\right) \) ו-\( G_{2}=\left(V_{2},T,S_{2},P_{2}\right) \) בהתאמה (אני מניח שקבוצת הטרמינלים \( T \) משותפת לשתי השפות, אחרת לוקחים את קבוצת האיחוד של הטרמינלים של שתיהן). אז דקדוק עבור האיחוד ייבנה על ידי הוספת משתנה התחלתי חדש \( S \) עם כללי הגזירה \( S\to S_{1}|S_{2} \) ולקיחת כל המשתנים וכללי הגזירה של שני הדקדוקים; דקדוק עבור השרשור ייבנה על ידי הוספת משתנה התחלתי חדש \( S \) וכלל הגזירה \( S\to S_{1}S_{2} \); ודקדוק עבור סגור קלייני של \( L_{1} \) ייבנה על ידי \( S\to SS_{1}|\varepsilon \). כבר עשיתי את זה בפוסט הפותח שלי על שפות חסרות הקשר אבל למה לא לעשות שוב. תרגיל נחמד זה להוכיח את הסגירויות הללו עם אוטומט מחסנית במקום עם דקדוק (מהר מאוד תגלו שקבלה על ידי ריקון מחסנית נוחה יותר מאשר קבלה עם מצבים מקבלים כשרוצים לכתוב את זה פורמלית).

התכונה הבאה היא הומומורפיזם. עבור שפות רגולריות הוכחתי אותה באינדוקציית מבנה כי היה לשפות הרגולריות מבנה אינדוקטיבי פשוט. אני לא מכיר מבנה דומה עבור שפות חסרות הקשר, אבל למרבה המזל, עם דקדוקים ההוכחה ממש קלה. נניח ש-\( h:\Sigma\to\Gamma \) הוא הומומורפיזם וניקח דקדוק \( G=\left(V,\Sigma,S,P\right) \). נבנה דקדוק \( G^{\prime}=\left(V\cup\Sigma,\Gamma,S,P\cup P^{\prime}\right) \) שהתעלול בו הוא שמי שהיו טרמינלים בדקדוק הקודם הם עכשיו גם כן משתנים, ונוסיף להם כללי גזירה: לכל \( \sigma\in\Sigma \) נוסיף את כלל הגזירה \( \sigma\to h\left(\sigma\right) \). עכשיו, קחו את עץ הגזירה של מילה בדקדוק הזה, והסירו ממנו את העלים - קיבלתם עץ גזירה של מילה בדקדוק המקורי. יחד עם העלים, מה שקורה הוא שכל טרמינל מוחלף בערך ההומומורפיזם עליו - מה שצריך להיות.

ההוכחה עבור הצבה דומה מאוד. כזכור, הצבה היא מעין הרחבה של הומומורפיזם כך שלכל אות מתאימים שפה, לא מילה. לכל \( \sigma\in\Sigma \) נסמן את השפה שההצבה מעבירה את \( \sigma \) אליה ב-\( L_{\sigma} \). כדי שתהיה לנו תקווה כלשהי לכך שהצבה תהיה תכונת סגור אנחנו חייבים לדרוש ש-\( L_{\sigma} \) תהיה חסרת הקשר (למה?) ולכן יש לה דקדוק \( \left(V_{\sigma},T_{\sigma},S_{\sigma},P_{\sigma}\right) \). נוסיף לדקדוק שלנו את כל המשתנים, הטרמינלים וכללי הגזירה של כל דקדוק כזה, ואת כלל הגזירה \( \sigma\to S_{\sigma} \). עכשיו תסבירו לעצמכם למה זה עובד.

עוד תכונת סגור של שפות רגולריות הייתה היפוך. לא קשה להראות (באינדוקציה…) שאם ניקח דקדוק ונהפוך את הכללים שלו (כלומר, נחליף כל כלל \( A\to\alpha \) ב-\( A\to\alpha^{R} \)) נקבל דקדוק עבור השפה ההפוכה. זה מעניין, כי קשה לי לראות דרך טובה להוכיח את התכונה הזו בעזרת אוטומט מחסנית (אני מניח שאפשר להפוך חישובים עם אוטומט מחסנית, אבל בגלל הצורך להתעסק עם המחסנית זה הופך להיות מאוד טרחני ומעצבן).

התכונה הבאה היא הומומורפיזם הפוך, וכאן העניינים קצת מסתבכים. כזכור, אם \( h:\Sigma\to\Delta \) הוא הומומורפיזם ו-\( L\subseteq\Delta^{*} \), אז מגדירים \( h^{-1}\left(L\right)=\left\{ w\in\Sigma:h\left(w\right)\in L\right\} \). המטרה שלנו היא להראות שאם \( L \) חסרת הקשר, כך גם \( h^{-1}\left(L\right) \). אבל את זה אני לא יודע לעשות עם דקדוקים, לשם שינוי. הומומורפיזם היה קל, כי כל אות גזרה את התמונה של האות הזו; אבל בהומומורפיזם הפוך אני צריך איכשהו לקבץ אותיות לקבוצות ולהמיר את כולן למקור שלהן, וזה כבר נשמע כמו דקדוק תלוי הקשר ולא חסר הקשר. נו טוב, לא חייבים ללכת עם הראש בקיר - אפשר במקום זה להשתמש באוטומט מחסנית.

עבור שפות רגולריות, ההוכחה הייתה ממש קלה. לקחנו אוטומט עבור \( L \) ובנינו אוטומט חדש עבור \( h^{-1}\left(L\right) \) שפעל כך - על כל אות \( \sigma \) הוא ביצע “סימולציה” של האוטומט המקורי על \( h\left(\sigma\right) \). זה היה קל במיוחד, כי לא באמת היה צריך לבצע את צעדי הסימולציה במפורש - כבר בזמן בניית האוטומט ידענו בודאות לאן הם יביאו אותנו והגדרנו את פונקציית המעברים בהתאם, כלומר הגדרנו \( \delta^{\prime}\left(q,\sigma\right)=\hat{\delta}\left(q,h\left(\sigma\right)\right) \). האם זה עדיין יעבוד? לא. למה לא? כי עכשיו תוצאת הסימולציה תלוייה בשני דברים: גם במצב שבו האוטומט נמצא, אבל גם בתוכן המחסנית. ותוכן המחסנית זה משהו שלא ידוע מראש כשבונים את קידוד האוטומט, ויש אינסוף תכנים אפשריים למחסנית כך שאי אפשר לכסות את כל המקרים. לא, הפעם הסימולציה תהיה חייבת להתבצע “צעד צעד”. אם זה עדיין לא ברור למה, חשבו על הסיטואציה הבאה: \( h\left(0\right)=aaa \). אנחנו רוצים להריץ סימולציה על \( 0 \), כלומר להזין לאוטומט שאנחנו מסמלצים את \( aaa \) ולראות מה קורה, על ה-\( a \) הראשון האוטומט מרוקן את הסימן שהיה בראש המחסנית. זה אומר שהמשך החישוב תלוי לא רק ב-\( 0 \) שקראנו, במצב שהיינו בו ובמה שהיה אז בראש המחסנית, אלא גם במה שהיה מתחת לראש המחסנית. ומי יודע מה האוטומט עושה הלאה - אולי הוא מרוקן את המחסנית עם מסעי-\( \varepsilon \) עד שהוא מגיע בה לתו מסויים? כלומר, מה שיקרה הלאה תלוי בכל תוכן המחסנית, ואי אפשר להתכונן מראש לכל אינסוף המקרים האפשריים.

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

קרוב לודאי שאיבדתם אותי, אז בואו נסתכל על הבניה הפורמלית - אני מקווה שהיא תהיה ברורה יותר. בואו ניקח \( L\subseteq\Delta^{*} \) ואוטומט מחסנית בשבילה שמקבל על ידי ריקון: \( M=\left(Q,\Delta,\Gamma,q_{0},\perp,\delta,\emptyset\right) \). אני אבנה אוטומט חדש \( M^{\prime} \) שקבוצת המצבים שלו מוגדרת בצורה קצת מוזרה: \( \left\{ \left(q,w\right)\ |\ \exists\sigma\in\Sigma,u\in\Delta^{*}:h\left(\sigma\right)=uw\right\} \). פורמלית, המצבים שלי הם כל הזוגות של מצב מ-\( Q \) ומילה \( w\in\Delta^{*} \) שהיא סיפא של תמונה של \( h \) על אות כלשהי מ-\( \Sigma \). למה סיפות? הכי פשוט לראות דוגמה. נניח ש-\( h\left(0\right)=abca \). אז אחרי שהאוטומט שלי קורא \( 0 \), הוא יודע שהוא צריך להזין לאוטומט שהוא מסמלץ את \( abca \). עכשיו, אחרי שהוא מזין לאוטומט הזה את ה-\( a \) הראשון, הוא עדיין צריך לזכור את יתר הדברים שהוא רוצה להזין אליו - כלומר, המחרוזת \( bca \), שהיא סיפא של \( abca \). אחרי שהוא הזין את ה-\( b \) הוא נשאר עם \( ca \), וכן הלאה - הבנתם את העיקרון. בסופו של דבר הוא יישאר עם \( \varepsilon \) (שגם היא סיפא, של כל מילה) ואז הוא ידע שהגיע הזמן לקרוא אות חדשה מהקלט האמיתי שלו (או לסיים).

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

1. \( \delta^{\prime}\left(\left(q,\varepsilon\right),a,A\right)=\left\{ \left(\left(q,h\left(a\right)\right),A\right)\right\} \) - שימו לב שלא נוגעים כאן במחסנית ושהצעד הזה מתקיים רק כאשר החוצץ ריק.
2. \( \delta^{\prime}\left(\left(q,aw\right),\varepsilon,A\right)=\left\{ \left(\left(p,w\right),\alpha\right)\ |\ \left(p,\alpha\right)\in\delta\left(q,a,A\right)\right\} \) - שימו לב שכאן \( a\in\Gamma\cup\left\{ \varepsilon\right\} \), כלומר ייתכן לבצע צעד סימולציה של מסע-\( \varepsilon \) שלא משנה את תוכן החוצץ.

בואו נרפרף גם על ההוכחה שזה עובד, למרות שאני חושב שהבניה (אחרי שמבינים אותה) היא די משכנעת. הרעיון בהוכחה, כמו כמעט כל הוכחת “בניה” אחרת בנושא הזה, היא להראות שהסימולציה “מתנהגת כמו שאנחנו מצפים בכל הצעדים שלה”. פורמלית, ש-\( \left[\left(q,\varepsilon\right),w,\alpha\right]\vdash_{M^{\prime}}^{*}\left[\left(p,\varepsilon\right),\varepsilon,\beta\right] \) אם ורק אם \( \left[q,h\left(w\right),\alpha\right]\vdash_{M}^{*}\left[p,\varepsilon,\beta\right] \) (כאן אני שם את שמו של האוטומט ליד ה-\( \vdash \) כדי שנדע על חישוב באיזה מהם מדובר). אם הראינו את זה, העובדה ש-\( L\left(M^{\prime}\right)=h^{-1}\left(L\left(M\right)\right) \) מתקבלת מייד על ידי בחירת \( \alpha=\perp,\beta=\varepsilon,q=q_{0} \), כי מצד אחד אם \( w\in L\left(M^{\prime}\right) \) אז נקבל ש-\( h\left(w\right)\in L\left(M\right) \) ולכן \( w\in h^{-1}\left(L\left(M\right)\right) \); ומצד שני אם \( w\in h^{-1}\left(L\left(M\right)\right) \) זה אומר ש-\( h\left(w\right)\in L\left(M\right) \) ולכן קיימת ריצה מקבלת של \( h\left(w\right) \) ב-\( L\left(M\right) \) וממנה אפשר לקבל ריצה מקבלת של \( w \) ב-\( L\left(M^{\prime}\right) \).

ההוכחה היא באינדוקציה על האורך של \( w \). עבור \( \left|w\right|=0 \) נקבל שצריך להוכיח כי \( \left[\left(q,\varepsilon\right),\varepsilon,\alpha\right]\vdash_{M^{\prime}}^{*}\left[\left(p,\varepsilon\right),\varepsilon,\beta\right] \) אם ורק אם \( \left[q,\varepsilon,\alpha\right]\vdash_{M}^{*}\left[p,\varepsilon,\beta\right] \) - זה נראה אולי טריוויאלי, אבל בעצם זה לא ממש טריוויאלי - זה אומר ש-\( M^{\prime} \) מסמלץ כמו שצריך את מסעי ה-\( \varepsilon \) של \( M \). רק כדי להוכיח את הטענה הזו נצטרך עוד אינדוקציה, על אורך החישוב. אבל למי יש כוח אז נעזוב את זה.

עכשיו, נניח נכונות עבור מילים מאורך \( n \) ונוכיח עבור מילים מאורך \( n+1 \). כאן ישתלם לנו לפרק חישובים לפי הצעד הראשון וכל מה שאחריו. כלומר, נניח ש-\( \left[\left(q,\varepsilon\right),aw,\alpha\right]\vdash_{M^{\prime}}^{*}\left[\left(p,\varepsilon\right),\varepsilon,\beta\right] \) עבור מילה \( aw \) כלשהי. מכיוון שבהתחלה החוצץ ריק, הצעד הראשון חייב להיות מהצורה 1. כלומר, אפשר לפרק את החישוב כך: \( \left[\left(q,\varepsilon\right),aw,\alpha\right]\vdash\left[\left(q,h\left(a\right)\right),w,\alpha\right]\vdash^{*}\left[\left(p,\varepsilon\right),\varepsilon,\beta\right] \). היינו רוצים להשתמש בהנחת האינדוקציה שלנו על \( \left[\left(q,h\left(a\right)\right),w,\alpha\right]\vdash^{*}\left[\left(p,\varepsilon\right),\varepsilon,\beta\right] \), אבל אי אפשר - כי הנחת האינדוקציה מתבססת על כך שהחוצץ ריק בקונפיגורציה השמאלית. לכן צריך להוכיח - שוב, באינדוקציה על אורך החישוב - ש-\( \left[\left(q,h\left(a\right),\varepsilon,\alpha\right)\right]\vdash_{M^{\prime}}^{*}\left[\left(p,\varepsilon\right),\varepsilon,\beta\right] \) אם ורק אם \( \left[q,h\left(a\right),\alpha\right]\vdash_{M}^{*}\left[p,\varepsilon,\beta\right] \). זה לא עד כדי כך קשה, כי המעברים היחידים האפשריים כל עוד החוצץ לא התרוקן הם מעברי \( \varepsilon \) (כי אין קלט). אחרי שסיימנו עם זה, ההמשך טבעי: נפרק את החישוב הראשוני שלנו לארבעה חלקים:

\( \left[\left(q,\varepsilon\right),aw,\alpha\right]\vdash\left[\left(q,h\left(a\right)\right),w,\alpha\right]\vdash^{*}\left[\left(s,\varepsilon\right),w,\gamma\right]\vdash^{*}\left[\left(p,\varepsilon\right),\varepsilon,\beta\right] \)

ובעזרת טענות העזר והנחת האינדוקציה רואים שזה מתקיים אם ורק אם ב-\( M \) מתקיים:

\( \left[q,aw,\alpha\right]\vdash^{*}\left[s,w,\gamma\right]\vdash^{*}\left[p,\varepsilon,\beta\right] \)

כפי שרצינו.

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