אוטומטים ושפות פורמליות/תכונות של שפות חסרות הקשר/למת הניפוח לשפות חסרות הקשר

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

מבוא

בדומה ללמת הניפוח עבור שפות רגולריות, נחשוב מה קורה כשאנו לוקחים מילה מאד מאד ארוכה. למשל, ארוכה יותר מאשר כל כללי היצירה של הדקדוק, $|x|\geq |P|$. מכיוון שיש יותר אותיות מאשר כללי יצירה, קיים כלל יצירה שחוזר על עצמו. הבעיה, שאם זהו התנאי היחידי, לא ברור איך ניתן לנפח, ומה ה"חזרה" שמתרחשת. למשל, נביט דקדוק שמייצר את המילה 0000. ייתכן שהדקדוק יצר את הפסוקית SSSS וממנה את המילה על-ידי שימוש בכלל $S\to 0$. למרות שאותו כלל חזר על עצמו 4 פעמים, לא ברור איך ניתן ליצור "ניפוח".

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

כעת נוכל לנפח: נניח שיש משתנה R שבתת-העץ הנוצר ממנו ($T_{1}$) קיים המשתנה R שוב (שממנו יוצא תת-עץ נוסף, שנקרא לו $T_{2}$). מילה חוקית בשפה תהיה המילה המתקבלת מהחלפת תת-העץ ($T_{1}$) בתת העץ ($T_{2}$) - כלומר מחיקת כל האותיות שנוצרו מ-$T_{1}$, פרט לאלו שנוצרו מ-$T_{2}$ (זהו, ניפוח כלפי מטה). באופן דומה, נוכל להדביק את העץ $T_{1}$ במופע השני של R. כך נקבל שאת האותיות שנוצרו מ-$T_{1}$ אבל לא מ-$T_{2}$ (אלו שמחקנו בניפוח מטה), חוזרות על עצמן פעמיים, וביניהן האותיות הנוצרות על ידי העץ $T_{2}$.

הגדרת הלמה

משפט: תהי $L$ שפה ח"ה, אזי קיים מספר $n\in \mathbb {N}$ כך שלכל מילה $w\in L$ הארוכה מ-$n$, ניתן לכתוב את המילה בצורה $w=xuyvz$ כך שמתקיים: $|uyv|\leq n$ $|uv|>0$ $\forall i\geq 0,xu^{i}yv^{i}z\in L$

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

ההוכחה זהה לאמור מעלה. תהיה L שפה ח"ה ונניח כי בדקדוק המינימלי המתאר אותה קיימים $|V|=t$ משתנים, כאשר לכל משתנה יש לכל היותר $m$ כללי יצירה. אזי כל מילה אשר ארוכה מ$n=m^{t}$ יוצרת עץ בו קיים מסלול באורך יותר מ-$t$ מהשורש עד לעלה (נשים לה שזה אינו עץ בינארי, אלא עץ m-ארי, לכן כמות העלים הנדרשת הינה $m^{t}$ ולא $2^{t}$). במסלול הנ"ל, כאמור, קיים משתנה שחוזר על עצמו, ועל כן, ניתן להפעיל את אותם כללי היצירה של המופע הראשון במופע השני, וליצור ניפוח. נניח שהמופע השני יוצר את תת-המחרוזת $y$ ונסמן ב $u,v$ את תתי המחרוזות הנוצרות מהמופע הראשון של R, לפני ואחרי המחרוזת $y$ בהתאמה.

קיים מקרה קצה בו שתי המחרוזות $u,v$ ריקות. במקרה זה נחליף את המופע הראשון במופע השני. לא הפחתנו את כמות האותיות, אבל הקטנו את העץ. מאידך, בעץ עדיין יש לפחות $m^{t}$ עלים, וניתן לחזור על ההוכחה, עד שאחת ממחרוזות אלו תהיה לא-ריקה (תהליך זה חייב להסתיים כי מדובר בעץ סופי.)

דוגמא

הראה כי השפה $L=\{0^{k}1^{k}2^{k}\mid k\geq 0\}$ אינה חסרת הקשר.

פתרון: נניח בשלילה כי השפה חסרת הקשר. אזי, על-פי הלמה, קיים מספר $n$ כך שמילים ארוכות מ-$n$ מקיימות את תנאי הלמה. נביט במילה $0^{n}1^{n}2^{n}\in L$ המילה ארוכה דיו ולכן קיימת דרך לפרק אותה למחרוזות $xuyvz$ כך ש $|uv|>0$ ו-$|uyv|<n$. מתנאי זה נובע שלא ייתכן שהמחרוזת $uyv$ מכילה גם אפסים גם אחדים וגם שתיים'ים. נביט במקרים השונים:

1. $uv$ מכילה רק סוג אחד של ספרות (למשל, ללא הגבלת כלליות, רק אפסים). אזי לפי הלמה גם המילה $xu^{2}yv^{2}z$ שייכת לשפה, אבל מילה זו מכילה יותר אפסים מאחדים, ולכן לא יכולה להיות ב-$L$.
2. $uv$ מכילה שני סוגי ספרות, בהג"כ, 0 ו 1. כנ"ל, אם ננפח אזי המילה $xu^{2}yv^{2}z$ מכילה רק n מופעים של 2 ויותר מ$2n$ אפסים ואחדים, בסתירה להיותה ב-$L$.

תרגיל : הוכח כי השפה $L=\{ww\mid w\in \{0,1\}^{n}\}$ אינה חסרת הקשר
על-ידי למת הניפוח, ניתן לקחת את המילה $0^{n}1^{n}0^{n}1^{n}$, ולחלק למקרים. אם מנפחים כמות שווה של אפסים ואחדים, ברור כי לפחות במקום אחד יישאר רצף של $n$ ספרות שלא נופחו, זו סתירה. אם כמות האפסים והאחדים שנופחה הינה שונה, מתקבל שהחצי הראשון והחצי השני אינם מתחילים באותה הספרה ועל-כן אינם זהים.

הפרק הקודם: תכונות סגור

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

הפרק הבא: צורות נורמליות לדקדוקים חסרי הקשר