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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

הרעיון האינטואיטיבי של למת הניפוח[עריכת קוד מקור | עריכה]

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

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

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

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

למת הניפוח לשפות חופשיות ההקשר[עריכת קוד מקור | עריכה]

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

1. \  |xvy|  \le n

2. \ |xy| \ge 1

3. לכל \ i \ge 0 מתקיים \ ux^ivy^iw \in L

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Bar-Hillel, Y.; Micha Perles, M. and Eli Shamir (1961). "On formal properties of simple phrase-structure grammars". Zeitschrift fur Phonetik, Sprachwissenschaft, und Kommunikationsforschung 14: 143–177