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

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

למת הניפוח לשפות חופשיות הקשר דומה ללמת הניפוח לשפות רגולריות, אך מורכבת יותר.

הלמה התגלתה על ידי יהושע בר-הלל, מיכה פרלס ואלי שמיר מהאוניברסיטה העברית.

הרעיון האינטואיטיבי של למת הניפוח

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

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

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

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

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

תהי $\ L$ שפה חופשית הקשר. אז קיים מספר טבעי $\ n$, כך שכל מילה $\ z$ ב-$\ L$, שאורכה לפחות $\ n$, ניתנת לפירוק מהצורה $\ z=uxvyw$, באופן שמתקיימים התנאים האלה:

1. $\ |xvy|\leq n$

2. $\ |xy|\geq 1$

3. לכל $\ i\geq 0$ מתקיים $\ ux^{i}vy^{i}w\in L$

יכול להיות מצב בו $\ u=\varepsilon$ או $\ v=\varepsilon$ או $\ w=\varepsilon$.

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

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

התנאי השלישי מתאר את הניפוח עצמו: עבור כל מספר שכפולים (כולל 0) של הקטעים הניתנים לניפוח, מקבלים מילה השייכת לשפה.

ראו גם

• למת הניפוח לשפות רגולריות
• תורת האוטומטים - מונחים

לקריאה נוספת

• שמואל זקס ונסים פרנסיז, ‏אוטומטים ושפות פורמליות ב, האוניברסיטה הפתוחה, 2000, עמ' 166–181

קישורים חיצוניים

• גדי אלכסנדרוביץ, שפות חסרות הקשר - למת הניפוח, הלמה של אוגדן ושפות רב משמעיות, בבלוג "לא מדויק"