הוכחת אי־רגולריות – למת הניפוח

ניסוח הלמה

תהי L שפה רגולרית. אז קיים מספר טבעי p (קבוע הניפוח) כך שלכל מילה w ∈ L עם |w| ≥ p, ניתן לפרק את w לשלושה חלקים w = xyz המקיימים:

1. |xy| ≤ p (הפירוק נמצא בתחילית של אורך לכל היותר p).
2. |y| ≥ 1 (החלק האמצעי לא ריק).
3. לכל i ≥ 0: xyⁱz ∈ L (אפשר "לנפח" את y כמה פעמים שרוצים, או להסיר אותו).

אינטואיציה: אם DFA עם p מצבים קורא מילה ארוכה ≥ p, אז לפי עקרון שובך היונים הוא בהכרח חוזר למצב כלשהו. הקטע שבין שתי הביקורים – זה y – ניתן לחזור עליו כמה פעמים בלי שהמסלול ישתנה.

תבנית הוכחת אי־רגולריות ב־5 צעדים

נניח שרוצים להוכיח ש־L אינה רגולרית. תמיד עוקבים אחר אותו מבנה לוגי:

1. הנחה לשלילה – "נניח ש־L רגולרית".
2. קבלת p – "מהלמה: קיים p, קבוע הניפוח של L".
3. בחירת w חכמה – בוחרים מילה w ∈ L באורך ≥ p שתעבוד נגד כל פירוק. כאן נמצאת רוב היצירתיות.
4. ניתוח כל הפירוקים – "תהי w = xyz פירוק שמקיים את שלושת תנאי הלמה". משתמשים בתנאים (1) ו־(2) כדי לתאר את y במדויק.
5. הגעה לסתירה – מוצאים i (לרוב i = 0 או i = 2) כך ש־xyⁱz לא שייכת ל־L. סתירה ל־(3). ⇒ ההנחה שגויה, L לא רגולרית.

דוגמה קלאסית: L = {aⁿbⁿ | n ≥ 0}

נוכיח של־L אינה רגולרית.

1. הנחה

נניח בשלילה ש־L רגולרית.

2. קבלת p

תהי p קבוע הניפוח של L מלמת הניפוח.

3. בחירת w

בוחרים w = aᵖbᵖ. ברור ש־w ∈ L (n = p) ו־|w| = 2p ≥ p.

4. ניתוח הפירוק

תהי w = xyz פירוק כלשהו המקיים את התנאים. מתנאי (1): |xy| ≤ p. כלומר xy נמצא כולו בתוך p ה־a הראשונים. לכן y מכיל רק a-ים. מתנאי (2): |y| ≥ 1, ולכן y = a^k עבור k ≥ 1.

5. סתירה

נבחר i = 2. אז

xy²z = a^p+kbᵖ

שכן הוספנו k אותיות a נוספות. אבל מספר ה־a (p+k) שונה ממספר ה־b (p), כי k ≥ 1. לכן xy²z ∉ L – בסתירה לתנאי (3) של הלמה. ⇒ L אינה רגולרית. ∎

למה בחרנו דווקא aᵖbᵖ?

הבחירה הזו מבטיחה ש־xy ייפול תמיד באזור ה־a הראשונים בלבד (כי |xy| ≤ p), וכך y מוגבל ל־a-ים בלבד. זה מצמצם את כל הפירוקים האפשריים למקרה אחד שקל לתקוף.

טעות נפוצה: לבחור w = aᵖbᵖ ולנסות מיד לעבוד עם b. לא ניתן – כי |xy| ≤ p אומר ש־xy נגמר לפני שמתחילים ה־b. בחרו תמיד מילה שהאות החלשה נמצאת ב־p הראשונים.

דוגמאות נוספות לשפות לא רגולריות

• {a^n² | n ≥ 0} – פלינדרומים על אלפבית של 2 אותיות לפחות.
• {ww | w ∈ {a,b}*} – מילים שמורכבות מהכפלה של עצמן.
• {aⁱb^j | i < j} – יותר b-ים מ־a-ים.
• {a^p | p ראשוני} – אורכים ראשוניים.

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

טיפ פסיכולוגי: זה משחק נגד יריב

אתם בוחרים את w; היריב בוחר את הפירוק x, y, z (כל פירוק חוקי שיתאים לו); אתם בוחרים את i ומכריחים סתירה. אם הצלחתם לבחור w שלכל פירוק חוקי קיים i שמוציא את xyⁱz מהשפה – ניצחתם.