למת הניפוח עבור שפות רגולריות
למת הניפוח עבור שפות רגולריות
שפה של מלים סופיות מעל א״ב סופי נקראת רגולרית אם קיים אוטומט דטרמיניסטי סופי (DFA) שמזהה אותה. במאמר זה נתאר את למת הניפוח עבור שפות רגולריות, ונדגים את השימוש בה בשביל להוכיח אי-רגולריות של שפה נתונה. אכן, מדובר באחד הכלים שבעזרתם ניתן להוכיח ששפה מסויימת אינה רגולרית. מאמר זה מיועד לסטודנטים המכירים את המושגים הבאים:
1- שפה של מלים סופיות מעל א״ב סופי.
2- אוטומט דטרמנסטי סופי (DFA).
למטה, מופיע הניסוח הפורמלי של הלמה:
1- \(|y| > 0\).
2- \(|xy|\leq p\).
3- \(\forall i \in \mathbb{N} \cup \{0\}, \ xy^iz \in L\).
עכשיו בוא נעכל את הלמה ביחד. הטקסט המתחיל אחרי ה ״אזי״ (״קיים קבוע ניפוח...״) אומר שניתן לנפח את השפה \(L\). לכן אפשר לחשוב על הלמה בצורה הבאה:
\(L\) שפה רגולרית \(\leftarrow\) ניתן לנפח את \(L\)
בשביל להבין את הלמה, צריך להבין מה זה אומר לנפח את \(L\): זה אומר שיש קבוע ניפוח טבעי חיובי \(p\) כך שלכל מילה מספיק ארוכה \(w\) ב \(L\), יש חלוקה לשלושה מלים \(w = xyz\) כך שהתנאים 1, 2 ו- 3 מתקיימים. התנאי הראשון אומר שהחלוקה של \(w\) היא כזו ש \(y\) אינה המילה הריקה, התנאי השני אומר שהאורך של \(xy\) ביחד הוא לכל היותר \(p\), ולבסוף התנאי השלישי אומר שניתן לנפח \(i\) פעמים את התת-מילה \(y\) ולהישאר בשפה \(L\).
שימוש בלמת הניפוח בשביל להסיק אי-רגולריות של שפה נתונה
אחת הדוגמאות הקלאסיות של שפה לא רגולרית \(L\), כלומר שפה שאין עבורה DFA, היא שפת המלים שיש בהן מספר שווה של אפסים ואחדים. פורמלית, \(L\) מוגדרת מעל הא״ב הבינרי \(\Sigma = \{0, 1 \}\) והיא מכילה אך ורק את המלים \(w\) שיש בהן מספר שווה של אפסים ואחדים:
\(\\L = \{ w \in \{ 0, 1\}^*: \#_0(w) = \#_1(w) \}\), כאשר הסימן \(\#_j(w)\) קוראים כ ״מספר ה \(j\)-ים במילה w״.
דיון לא פורמלי: אינטואיטיבית, השפה \(L\) שהגדרנו אינה רגולרית. למה? כי אוטומט דטרמנסטי סופי (DFA) לא יכול ״לספור״ כמה אפסים ואחדים יש במילת הקלט בשביל להשוות אותם. או ליתר דיוק, הזכרון של אוטומט מוגבל ע״י מספר המצבים שיש בו. אפשר לחשוב על זה בצורה הבאה. אני נותן לכם אתגר, בעצם משימה בלתי אפשרית, של לנסות לבנות DFA עבור השפה \(L\). אתם לוקחים את האתגר הזה הביתה, חושבים המון זמן, ומחזירים לי אוטומט \(A\) שאמור לזהות את \(L\). מה שאני עושה עכשיו, זה לקחת את האוטומט שהצעתם \(A\) ולהסתכל כמה מצבים יש בו. מכיוון שאנו מדברים על אוטומטים סופיים, מספר המצבים ב \(A\) הינו סופי, בוא נניח 100. ועכשיו בשביל להוכיח לכם ש \(A\) אינו מזהה את \(L\), אני נותן ל \(A\) קלט מספיק ארוך \(w\) בשביל לבלבל אותו! אפשר לחשוב למשל על הקלט \(w = 0^{100}1^{100}\) שהוא אכן בשפה \(L\), כלומר לטענתכם, \(A\) אמור לקבל את \(w\). הקטע הוא שהמילה \(w = 0^{100}1^{100}\) שבחרתי היא בעייתית במובן הזה שמספר האפסים שהיא מכילה הוא כמספר המצבים באוטומט \(A\). לכן, הריצה של \(A\) על הרישא \(0^{100}\)מספיק ארוכה ובהכרח סוגרת מעגל. משמעות הדבר היא שהריצה המקבלת \(r\) של \(A\) על \(w\) עוברת במעגל לא ריק המסומן רק ע״י אפסים. אם אני חוזר על המעגל הזה יותר מפעם אחת, או פשוט משמיט אותו מהריצה \(r\), אני עדיין אקבל ריצה מקבלת על קלט שיש בו מספר שונה של אפסים ואחדים, בסתירה לכך ש \(A\) מזהה את \(L\).
הקטע הזה שתיארתי בדיון הלא פורמלי, אני יכול לבצע עבור כל אוטומט \(A\) שמתיימר לזהות את השפה \(L\). ואפשר לחשוב על זה כסוג של נסיון הוכחה של האי-רגולריות של \(L\). אפשר לחשוב על למת הניפוח כהכללה של שיטה זו. בעצם, ההוכחה הפורמלית של הלמה (שלא נציג במאמר זה) עוברת דרך שיקולים דומים.
כרגע, נוכיח בצורה פורמלית, דרך שימוש בלמת הניפוח, שהשפה \(\\L = \{ w \in \{ 0, 1\}^*: \#_0(w) = \#_1(w) \}\) אינה רגולרית. ההוכחה הולכת דרך השלילה.
הוכחה פורמלית: נניח בשלילה שהשפה \(L\) רגולרית. לכן, ע״פ למת הניפוח קיים קבוע ניפוח \(0<p\) עבור \(L\). נתבונן במילה \(w = 0^p 1^p\). המילה \(w\) היא אכן בשפה \(L\), והיא מספיק ארוכה, כלומר \(|w| \geq p\). לכן, ע״פ למת הניפוח, קיימת ל \(w\) חלוקה לשלושה מלים \(w = xyz\) כך שהתנאים הבאים מתקיימים:
1- \(|y| > 0\).
2- \(|xy|\leq p\).
3- \(\forall i \in \mathbb{N} \cup \{0\}, \ xy^iz \in L\).
מכיוון ש \(w = 0^p 1^p\) נקבל שה \(p\) אותיות הראשונות ב \(w\) לא מכילות אחדים. לכן תנאי 2 גורר שמילה \(xy\) מורכבת רק מאפסים. כעת, ננפח את המילה \(w\) למטה, כלומר נשתמש בתנאי 3 עבור \(i=0\) ונקבל שהמילה \(xy^0z = xz \) נמצאת בשפה \(L\). המילה \(xz\) היא פשוט המילה \(w\) אחרי שהשמטנו ממנה את התת-מילה \(y\), לכן מכיוון ש \(y\) מורכבת רק מאפסים נקבל ש
\(xy^0z = xz = 0^{p-|y|}1^p\). לבסוף, מתנאי 1, נקבל שהמילה \(xz\) מכילה פחות אפסים מאשר אחדים, בסתירה לכך שהיא מילה בשפה \(L\).
הערות:
1- אפשר בהוכחה הנ״ל לנפח עם \(i >1\) (משאיר לקורא).
2- ההוכחה דרך למת הניפוח הולכת בשלילה. אפשר לחשוב עליה בדומה לדיון הלא פורמלי. אתם טוענים ש \(L\) רגולרית, וזורקים עלי קבוע ניפוח \(p\). כעת, המטרה שלי היא להוכיח לכם שאתם טועים דרך זה שאני בוחר מילה \(w\) בעייתית: מילה בשפה שהיא מספיק ארוכה, כך שכל חלוקה של \(w\) לשלושה מלים אינה מקיימת את שלושת התנאים של הלמה בו-זמנית. וזה החלק הקשה בהוכחות מסוג זה - לעלות על המילה הבעייתית!
למת הניפוח אינה מאפיינת שפות רגולריות
כפי שכבר ראינו, למת הניפוח אומרת שניתן לנפח כל שפה רגולרית:
\(L\) שפה רגולרית \(\leftarrow\) ניתן לנפח את \(L\)
אבל הכיוון השני אינו בהכרח נכון. כלומר, קיימות דוגמאות לשפות לא רגולרית \(L\) שניתן לנפח. לכן, למת הניפוח לא מאפיינת שפות רגולריות. משמעות הדבר היא שלמרות שלמת הניפוח מהווה כלי להוכחת אי-רגולריות של שפה נתונה, אי אפשר להשתמש בה בשביל להוכיח ששפה מסויימת היא אכן רגולרית. לכן תשתמשו בה בזהירות!