בשיעור זה נוכיח שלפעמים שום אוטומט סופי אינו מספיק. נלמד להבחין בין קידומות באמצעות המשך מתאים, להשתמש בלמת הניפוח ולבודד שפה קשה בעזרת תכונות סגירות. נבנה הוכחות ולא נסתפק באמירה “צריך לספור”.
מטרות וידע קודם
נדרשת היכרות עם מצבים, שפות ופעולות משיעורים 1–7. נוכיח טענה על כל DFA אפשרי, ולא רק ניכשל בניסיון לבנות אחד. לכל DFA יש מספר סופי של מצבים; לכן אם נציג אינסוף קידומות שחייבות להסתיים במצבים שונים, נקבל סתירה.
דוגמה פתורה 1 — קידומות נבדלות
נבחן \(L=\{a^n b^n\mid n\ge0\}\). נבחר את הקידומות \(\varepsilon,a,a^2,a^3,\ldots\). לכל שני מספרים \(i\ne j\), ההמשך \(b^i\) מבדיל בין \(a^i\) לבין \(a^j\): המילה \(a^ib^i\) בשפה ואילו \(a^jb^i\) אינה בשפה.
אילו שתי הקידומות היו מביאות לאותו מצב, קריאת אותו המשך הייתה מביאה לאותה תשובת קבלה. לכן כל קידומת דורשת מצב משלה. אין DFA עם אינסוף מצבים, ולכן השפה אינה רגולרית.
תבנית הוכחה שימושית: משפחה אינסופית של קידומות; בחירה של שתי קידומות שונות; המשך אחד שמקבל בדיוק אחת מהן; מסקנה שהן חייבות להיות במצבים שונים. ההמשך רשאי להיות תלוי בזוג שבחרנו.
דוגמה פתורה 2 — למת הניפוח
הלמה אומרת: אם \(L\) רגולרית, קיים מספר \(p\ge1\) כך שלכל \(w\in L\) שאורכה לפחות \(p\), קיים פירוק \(w=xyz\) המקיים:
\[|xy|\le p,\qquad |y|>0,\qquad \forall t\ge0:\ xy^tz\in L.\]הסיבה: ב־\(p\) סימני הקלט הראשונים, DFA עם \(p\) מצבים מבקר ב־\(p+1\) מצבים כשכוללים את ההתחלה. מצב כלשהו חוזר. החלק \(y\) הוא לולאה שאפשר לחזור עליה או לדלג על ביצועה.
נוכיח שוב ש־\(\{a^n b^n\}\) אינה רגולרית. נניח שהיא רגולרית ויהי \(p\) מספר הניפוח. נבחר \(w=a^pb^p\). לכל פירוק חוקי, \(y=a^r\) עבור \(1\le r\le p\), כי \(xy\) כולו בתוך בלוק ה־a. נבחר \(t=0\): מתקבלת \(a^{p-r}b^p\), שאינה בשפה. סתירה.
אנחנו בוחרים את המילה, אבל איננו בוחרים את הפירוק. צריך לפסול את כל הפירוקים החוקיים. כמו כן, הלמה נותנת תנאי הכרחי לרגולריות, לא מבחן שמוכיח רגולריות כשלא הצלחנו למצוא סתירה.
דוגמה פתורה 3 — ספירה בתוך מילים חופשיות
מטלה 3 שאלה 1א נותנת:
\[K=\{w_1b^nw_2\mid n\ge1,\ w_1,w_2\in\{a,c\}^*,\ \#_a(w_1)=\#_c(w_2)\}.\]חותכים בשפה הרגולרית \(a^*bc^*\) ומקבלים בדיוק \(\{a^ibc^i\mid i\ge0\}\). השפה הזאת אינה רגולרית: הקידומות \(a^i\) נבדלות באמצעות ההמשך \(bc^i\). אילו \(K\) הייתה רגולרית, גם החיתוך היה רגולרי לפי סגירות, בסתירה לתוצאה. האותיות ה”חופשיות” במקור אינן מבטלות את הצורך בהשוואה.
דוגמה פתורה 4 — אי־שוויון גם דורש זיכרון
מטלה 3 שאלה 1ב: \(H=\{a^ib^jcd^k\mid i\ge2,\ j>k\ge0\}\). ניקח קידומות \(u_t=a^2b^{t+1}\) לכל \(t\ge0\). עבור \(s<t\), ההמשך \(cd^t\) מקבל את \(u_t\) כי \(t+1>t\), ודוחה את \(u_s\) כי \(s+1\le t\). לכן גם כאן יש אינסוף קידומות נבדלות, והשפה אינה רגולרית. ה־c מופיעה פעם אחת; אין להוסיף לה חזקה שאינה במקור.
איך בוחרים דרך הוכחה?
אם קל למצוא משפחת קידומות והמשך שמבדיל ביניהן, השתמשו בה. אם יש בלוקים ארוכים שהניפוח מוכרח ליפול באחד מהם, הלמה נוחה. אם יש רעש מסביב להשוואה, חיתוך רגולרי עשוי לבודד אותה. אין להסיק ששפה אינה רגולרית רק משום שהיא מכילה תת־שפה שאינה רגולרית: גם \(\Sigma^*\) מכילה כאלה.
תרגול
1. יחס שניים לאחד
הוכיחו ש־\(\{a^n b^{2n}\mid n\ge0\}\) אינה רגולרית.
רמז ופתרון
רמז: שנו רק את ההמשך בדוגמה 1. פתרון: הקידומות \(a^i\) נבדלות באמצעות \(b^{2i}\). הוא משלים את \(a^i\) למילה בשפה, אך אינו משלים את \(a^j\) עבור \(j\ne i\). נדרשים אינסוף מצבים.
2. אותו מונה או שני מונים?
השוו בין \(\{a^2c^{k+2}b^k\mid k\ge0,\ k\bmod2=0\}\) לבין הגרסה שבה מספר ה־b הוא \(m\ge0\) בלתי תלוי.
רמז ופתרון
רמז: שמרו על תנאי הזוגיות בבחירת קידומות. פתרון: בראשונה הקידומות \(a^2c^{2r+2}\) נבדלות באמצעות \(b^{2r}\), ולכן אינה רגולרית. השנייה היא \(\{aa\}\{cc\}(\{cc\})^*(\{b\})^*\), שרשור וכוכב של שפות סופיות, ולכן רגולרית. ההבדל הוא התלות, לא עצם השימוש בחזקות.
3. פירוק שנבחר בטעות
תלמיד בוחר \(x=\varepsilon,y=a^p,z=b^p\) ואומר שהניפוח מוציא מהשפה. מה חסר?
רמז ופתרון
רמז: הלמה מבטיחה שקיים פירוק, לא שכל פירוק עובד. פתרון: פסילת פירוק אחד אינה מספיקה. צריך לומר שלכל פירוק חוקי \(y=a^r\) עם \(r>0\), ואז להראות שהוצאתו משבשת את השוויון. זהו בדיוק הצעד בדוגמה 2.