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

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

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

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

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

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

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

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

1. $|uv|\leq n$

2. $|v|\geq 1$

3. לכל $i\geq 0$ טבעי מתקיים $z_{i}=uv^{i}w\in L$

כמובן, ייתכן מצב בו $u=\varepsilon$ או $w=\varepsilon$.

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

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

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

דוגמאות

שפה שאינה ניתנת לניפוח

השפה $L_{ab}=\left\{a^{i}b^{i}|i\in \mathbb {N} \right\}$ ידועה כשפה לא רגולרית. נראה כיצד ניתן להשתמש בלמת הניפוח כדי לראות זאת.

נניח בשלילה כי השפה כן רגולרית, אז קיים ה- $n$ שקיומו מובטח על ידי המשפט. נביט במילה $a^{n}b^{n}$. אורכה גדול מ-$n$ (הוא בדיוק $2n$) ולכן המילה ניתנת לניפוח, כלומר קיים לה פירוק $\ uvw$ כמתואר.

כעת, מכיוון ש-$|uv|\leq n$ בהכרח $uv=a^{k}$, שכן $n$ האותיות הראשונות במילה הן $a$-ים. לכן $v=a^{t}$ כאשר $1\leq t\leq n$ (שהרי מהלמה $|v|\geq 1$).

כעת נביט על המילה $uv^{0}w$, כלומר $uw$. מילה זו שייכת לשפה על פי למת הניפוח. אבל היא בדיוק מהצורה $\ a^{n-t}b^{n}$ ומכיוון ש-$t\geq 1$ הרי שבהכרח $n-t\neq n$, והגענו לסתירה, כי כל המילים בשפה הן כאלו שבהן מספר ה-$a$-ים וה-$b$-ים זהה. לכן $\ L$ אינה שפה רגולרית.

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

נביט בשפה $L=\left\{ab\right\}$, כלומר השפה שמכילה מילה בודדת: $ab$. ברור כי לא ניתן לנפח את השפה הזו - מכיוון שקיימת בה רק מילה אחת, אם נגדיל או נקטין את מספר האותיות בה נקבל מילה אחרת, שאינה שייכת לשפה. עם זאת, השפה רגולרית, כי כל שפה סופית היא רגולרית.

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

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

רעיון ההוכחה

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

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

המחשת הוכחת הלמה

כעת, אם $z$ היא מילה שאורכה לפחות $\ n$, בריצתו של האוטומט עליה הוא מבצע לפחות $n$ צעדים (בכל צעד נקראת אות אחת מהמילה) ולכן עובר ב-$n+1$ מצבים של האוטומט. מכיוון שיש באוטומט רק $n$ מצבים, נובע מעקרון שובך היונים שקיים מצב $q$ שהאוטומט מבקר בו פעמיים תוך כדי קריאת $n$ האותיות הראשונות.

כעת מפרקים את $z$ כדלהלן: בתור $u$ בוחרים את הרישא של המילה אותה קורא האוטומט עד שהוא מגיע לראשונה למצב $q$. בתור $v$ בוחרים את המשך המילה אותה האוטומט קורא עד שהוא חוזר אל המצב $q$. בתור $w$ בוחרים את שאר המילה.

תנאי מספר 1 מתקיים בבירור שכן $u,v$ נבחרו שתיהן מתוך $n$ האותיות הראשונות של המילה. גם תנאי מספר 2 מתקיים שכן כדי לבקר פעמיים במצב $q$ על האוטומט לקרוא לפחות אות אחת מהרגע בו ביקר במצב בפעם הראשונה ועד שהוא מבקר בו בפעם השנייה.

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

ראו גם

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

לקריאה נוספת

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

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

• גדי אלכסנדרוביץ', למת הניפוח לשפות רגולריות, באתר "לא מדויק", 3 בפברואר 2015