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

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

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

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

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

תהי L שפה חופשית הקשר. יש מספר טבעי n כך שלכל מילה z ב־L שאורכה לפחות n יש פירוק z = u x v y w שמקיים: |xvy| קטן או שווה ל־n, |xy| גדול או שווה ל־1, ולכל i≥0 המחרוזת u x^i v y^i w שייכת ל־L. יכול להיות שאחד החלקים u, v או w הוא המחרוזת הריקה.

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

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

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

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

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

הלמה הומצאה על ידי יהושע בר-הלל, מיכה פרלס ואלי שמיר.