למת הניפוח לשפות רגולריות

למת הניפוח נועדה להראות ששפה L מסוימת אינה רגולרית. היא נותנת תנאי הכרחי לרגולריות: אם שפה רגולרית, אז קיימת דרך "לנפח" מילים גדולות בה. הלמה נוסחה על ידי יהושע בר-הלל, מיכה פרלס ואלי שמיר.


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


לשפה רגולרית L קיים מספר טבעי n כך: כל מילה z ב-L שאורכה לפחות n ניתנת לפירוק z = u v w כך ש:
1. |uv| ≤ n, כלומר החלק שאפשר לנפח נמצא בתוך n האותיות הראשונות.
2. |v| ≥ 1, הקטע הניתן לניפוח אינו ריק.
3. לכל i ≥ 0 המילה u v^i w שייכת ל-L, אפשר לשכפל את v כל מספר פעמים, גם 0.

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



השפה L_ab = { a^i b^i | i∈ℕ } מכילה מילה המורכבת מ-i אותיות a ולאחריהן i אותיות b. אם נניח שהיא רגולרית ונבחר n, נקח את המילה a^n b^n. לפי הלמה מקיימת פירוק z = u v w כאשר uv בתוך החלק של ה-a-ים, ולכן v מורכב רק מ-a. אם נשתיק את v (i=0) נקבל מילה עם פחות a-ים מאשר b-ים, לכן אינה ב-L_ab. זו סתירה, ולכן L_ab אינה רגולרית.


השפה {ab} היא רגולרית אך לא ניתנת לניפוח בפועל, כי היא מכילה רק מילה אחת. זה לא סותר את הלמה, כי אפשר לבחור n גדול מדי כך שאין מילה ארוכה מ-n, ואז התנאים מתקיימים באופן ריק.


עבור שפה רגולרית אינסופית בוחרים n שווה למספר מצבי האוטומט שמקבל את השפה. כל מילה ארוכה מ-n גורמת לאוטומט לעבור יותר מצבים מאשר יש לו, ולכן יהיה מצב שמבקרים בו פעמיים בתוך החלק הראשון של המילה. מחלקים את המילה לפי הפעם הראשונה והשנייה שבה מבקרים באותו מצב, וכך מקבלים את u, v, w. השכפול או המחיקה של v לא ישפיעו על המשך הריצה אחרי אותו מצב, ולכן כל u v^i w תתקבל גם היא על ידי האוטומט.

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


אם מכונה קטנה יכולה לזהות שפה, אז במילים ארוכות יש קטע שחוזר. אפשר להוציא את הקטע הזה או לחזור עליו, והמילה תישאר בשפה.


אם השפה רגולרית, יש מספר n כזה: כל מילה ארוכה מ-n מתחלקת ל-u, v, w כך ש-
1. החלק u ו-v נמצאים בתוך n האותיות הראשונות.
2. v לא ריק. כלומר יש בו לפחות אות אחת.
3. אפשר לחזור על v כל מספר פעמים, גם 0, והמילה שנוצרת תהיה עדיין בשפה.



השפה שמכילה מילה עם כמה a ואז אותו מספר b, למשל aaabbb. אם ננסה לנפח אותה, נקבל פחות a-ים או יותר, וזה לא מתאים. לכן השפה הזאת לא רגולרית.


השפה שכוללת רק את המילה ab רגולרית. לא ניתן לנפח אותה כי אין מילים אחרות. זה לא סותר את הלמה.


לוקחים את מספר המצבים של המכונה כ-n. במילה ארוכה המכונה חייבת לחזור על מצב. כך שולפים את v, וקובעים שאפשר לחזור עליו או למחוק אותו בלי לשבור את קבלת המילה.