בשיעור זה נסווג שפות לפי כוח הזיכרון הדרוש להן. נראה שמחסנית יכולה להשוות כמויות אך אינה פותרת כל דרישת ספירה; נבנה אוטומט להשוואת כמויות בסדר חופשי ונוכיח מדוע שפות מסוימות אינן חופשיות הקשר.
מטרות וידע קודם
נשלב הוכחות משיעור 8 ובניות מחסנית משיעורים 10–11. שפה רגולרית מתקבלת באוטומט סופי. שפה חופשית הקשר היא שפה שניתנת לתיאור בדקדוק חופשי הקשר; לפי משפט שקילות, זו גם מחלקת השפות המתקבלות ב־PDA לא דטרמיניסטי במודל התאורטי הכללי. דקדוקים אינם נדרשים לפתרון המטלות כאן.
משפט השקילות מתייחס למודל PDA הכללי. הבניות שלנו מקיימות מגבלה נוספת: אין מעברי אפסילון. אין להסיק שכל שפה חופשית הקשר ניתנת לבנייה דטרמיניסטית, או שבניית PDA כללית שמצאנו בספר כבר עומדת במגבלות הקורס. כל אוטומט שנציג כאן ייבדק בנפרד.
כל שפה רגולרית חופשית הקשר: אפשר לדמות DFA בלי לשנות את המחסנית. ההכלה ממש, כי \(\{a^nb^n\}\) מתקבלת במחסנית אך אינה רגולרית. יש גם שפות שאינן חופשיות הקשר, כמו \(\{a^nb^nc^n\}\).
דוגמה פתורה 1 — יותר a מאשר b בסדר חופשי
מטלה 4 שאלה 4, \(L_4=\{w\mid\#_a(w)>\#_b(w)\}\). לא מספיק להעתיק את האוטומט ל־\(a^nb^n\): כאן baaa ו־ababaa מותרות. נשמור במחסנית את הערך המוחלט של ההפרש, ובמצב את סימנו.
התחלה Z (הפרש אפס); מקבל רק P (עודף a); N מציין עודף b. S מסמן את יחידת ההפרש הראשונה, ו־A את יתר היחידות. T בטבלה הוא S או A.
| מצב | קלט | ראש | פעולה | יעד |
|---|---|---|---|---|
Z |
a |
⊥ |
דחוף S |
P |
Z |
b |
⊥ |
דחוף S |
N |
P |
a |
T |
דחוף A |
P |
P |
b |
A |
שלוף A |
P |
P |
b |
S |
שלוף S |
Z |
N |
b |
T |
דחוף A |
N |
N |
a |
A |
שלוף A |
N |
N |
a |
S |
שלוף S |
Z |
בהרצת bbaaaba, ההפרשים הם \(0,-1,-2,-1,0,1,0,1\). המצבים בהתאם Z,N,N,N,Z,P,Z,P, ולכן מקבלים. כל צעד שומר את משמעות הסימן והגובה, ואין מעברי אפסילון. השפה חופשית הקשר. היא אינה רגולרית: הקידומות \(a^i\) עבור \(i\ge1\) נבדלות; עבור \(i<j\) ההמשך \(b^i\) דוחה את הראשונה ומקבל את השנייה.
המחסנית אינה חייבת לשמור את כל הקלט. כאן היא שומרת רק יחידות שטרם קוזזו, והמצב אומר לאיזה סימן יש עודף. האינווריאנט מסביר מדוע הבנייה עובדת גם כשהסימנים מעורבבים.
דוגמה פתורה 2 — שלושה בלוקים שווים
לשפות חופשיות הקשר יש למת ניפוח אחרת: אם \(L\) חופשית הקשר, קיים \(p\ge1\) כך שכל מילה בשפה שאורכה לפחות \(p\) ניתנת לפירוק \(w=uvxyz\) עם \(\lvert vxy\rvert\le p\), \(\lvert vy\rvert>0\), ולכל \(t\ge0\) מתקיים \(uv^txy^tz\in L\).
נבחר \(w=a^pb^pc^p\). החלון \(vxy\) אינו יכול לגעת גם בבלוק הראשון וגם בשלישי, כי ביניהם \(p\) סימני b. בניפוח כלפי מטה (\(t=0\)) מסירים לפחות סימן אחד ומשאירים לפחות אחד משלושת הבלוקים ללא שינוי. אם סדר הבלוקים נפגע, המילה ממילא אינה בשפה; ואם נשמר, הכמויות כבר אינן כולן שוות. זו סתירה לכל פירוק חוקי, ולכן השפה אינה חופשית הקשר.
דוגמה פתורה 3 — שפה שנראית כמו שתי השוואות
במטלה 4 מופיעה \(L_2=\{a^nb^na^m\mid n\ge m\ge0\}\). זו אינה חופשית הקשר. הרעיון “נשלוף עבור ה־b ואז נשווה גם לבלוק האחרון” מאבד את הספירה הראשונה ואינו הוכחה לבנייה אפשרית.
נוכיח בעזרת אותה למה, עם \(w=a^pb^pa^p\). חלון באורך לכל היותר \(p\) אינו יכול לגעת בשני בלוקי ה־a. נסמן ב־\(\alpha,\beta,\gamma\) את מספר הסימנים ש־\(v,y\) יחד תורמים לבלוק הראשון, האמצעי והאחרון. אם ניפוח פוגע בצורת הבלוקים, כבר קיבלנו סתירה; אחרת:
- אם \(\alpha\ne\beta\), ניפוח כלפי מעלה מפר את שוויון שני הבלוקים הראשונים.
- אם \(\alpha=\beta>0\), אז \(\gamma=0\). ניפוח כלפי מטה מקטין את שני הבלוקים הראשונים, ומשאיר את האחרון באורך \(p\); כעת \(m>n\).
- אם \(\alpha=\beta=0\), בהכרח \(\gamma>0\). ניפוח כלפי מעלה מגדיל רק את הבלוק האחרון ושוב \(m>n\).
בכל מקרה נמצא ניפוח לא חוקי. בניגוד ל־\(a^nb^n\), כאן דרישה נוספת לבלוק האחרון משנה את הסיווג.
מסכמים את סיווגי מטלה 4 שאלה 4
| שפה | סיווג | נימוק |
|---|---|---|
| \(L_1=\{(ab)^n(ab)^m\mid n\ge m\ge0\}\) | רגולרית | שווה ל־\(\{ab\}^*\), שיעור 9 |
| \(L_2=\{a^nb^na^m\mid n\ge m\ge0\}\) | לא חופשית הקשר | ההוכחה לעיל |
| \(L_3=\{a^nb^{2n}a^{n\bmod3}\mid n\ge0\}\) | חופשית הקשר ולא רגולרית | מחסנית ליחס 2:1 ומצב לשארית; פירוט להלן |
| \(L_4=\{w\mid\#_a(w)>\#_b(w)\}\) | חופשית הקשר ולא רגולרית | הבנייה וההוכחה בדוגמה 1 |
| \(L_5=L_2\cap L_3\) | רגולרית | שווה ל־\(\{\varepsilon\}\), שיעור 9 |
לבניית \(L_3\) דוחפים יחידה לכל a, ושומרים במצב את מספר ה־a מודולו 3. בשלב ה־b שולפים על כל b שני; השארית נשמרת במצב ללא שינוי. בשליפת S יודעים שהסתיימו \(2n\) סימני b, ומעבירים לשרשרת שקוראת בדיוק 0, 1 או 2 סימני a, לפי השארית. אם השארית 0, יעד השליפה עצמו מקבל. ההתחלה מקבלת את ε, אך אין אליה חזרה. כל מעבר צורך קלט. לאי־רגולריות, הקידומות \(a^{3i}\) נבדלות באמצעות \(b^{6i}\).
חופשיות הקשר אינן סגורות לחיתוך כללי: \(\{a^nb^nc^k\}\) ו־\(\{a^ib^nc^n\}\) חופשיות הקשר, אך חיתוכן הוא שלושה בלוקים שווים. הן כן סגורות לחיתוך עם שפה רגולרית. גם סגירות למשלים אינה מובטחת למחלקה הכללית.
תרגול
1. שפה אחת, שלוש דרכי ראייה
סווגו \(\{a^nb^{2n}\mid n\ge0\}\) והסבירו מדוע שתי המילים “לא רגולרית” אינן מספיקות כסיווג מלא.
רמז ופתרון
רמז: שליפה על כל b שני. פתרון: חופשית הקשר ולא רגולרית. אפשר לדחוף יחידה לכל a ולשלוף בכל b שני, עם סימן ראשון מיוחד ותחילה מקבלת לריקה. אי־רגולריות הוכחה בשיעור 8. “לא רגולרית” לבדה אינה מבדילה בין שפה שמחסנית מספיקה לה לשפה שאינה חופשית הקשר.
2. החיתוך ששובר סגירות
תארו מדוע כל אחת משתי השפות שבאזהרה חופשית הקשר, אף שחיתוכן אינו כזה.
רמז ופתרון
רמז: בכל אחת יש רק השוואה אחת ושאר בלוקים חופשיים. פתרון: בראשונה משווים a ל־b ואחר כך קוראים c כרצוננו; בשנייה קוראים a כרצוננו ואז משווים b ל־c. זו גם מסקנה מסגירות חופשיות הקשר לשרשור עם שפה רגולרית. בחיתוך חייבים לקיים את שתי ההשוואות באותה מילה, ולכן מקבלים \(a^nb^nc^n\).
3. היפוך במטלה 3
מדוע \(L_6=\{a^nb^mc^ma^n\mid m>n\ge0\}\) אינה רגולרית?
רמז ופתרון
רמז: בידדו את המילים שאין בהן a. פתרון: החיתוך עם \(\{b\}^*\{c\}^*\) הוא \(\{b^mc^m\mid m>0\}\), שאינה רגולרית באמצעות קידומות נבדלות. אילו \(L_6\) הייתה רגולרית, גם החיתוך היה רגולרי. אין צורך לקבוע כאן חופשיות הקשר כדי לענות לדרישת הסעיף במטלה 3.