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

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

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

הניסוח הכללי של הלמה לא קל לעיכול, אז בואו ניזכר לרגע מה קרה בניסוח הפשוט ואיך הגענו אליו. \( L \) מקיימת את הלמה אם קיים מספר טבעי \( n \) כך שכל מילה \( z\in L \) המקיימת \( \left|z\right|\ge n \) ניתנת לפירוק \( z=uvw \) כך ש-\( \left|uv\right|\le n \) ו-\( \left|v\right|\ge1 \) ו-\( uv^{i}w\in L \) לכל \( i\ge0 \). למה זה עובד? כי לוקחים את \( n \) להיות מספר המצבים באוטומט עבור \( L \) ומסתכלים על ריצה שמקבלת את \( z \). כבר אחרי \( n \) הצעדים הראשונים של הריצה יהיה מצב שחוזר על עצמו; מסמנים ב-\( u \) את מה שקראנו עד להגעה הראשונה למצב, ב-\( v \) את מה שקראנו כדי לעבור מהמצב אל עצמו, וב-\( w \) את יתר המילה. התנאי של ה-\( \left|uv\right|\le n \) נובע מכך שההגעה השניה שלנו למצב הזה היא במסגרת \( n \) הצעדים הראשונים.

אם כן, הרכיב המרכזי בהוכחה הוא העניין הזה של “ביצעת יותר מ-\( n \) צעדים? קבל מעגל!”. הנקודה החשובה היא שזה בכלל לא חשוב מתי הצעדים הללו מתבצעים - בהתחלה, באמצע, בסוף, עם פער ביניהם, בלי פער ביניהם - אם ניקח את ריצת האוטומט על מילה, ו”נעצור כדי להציץ” את הריצה \( n+1 \) פעמים, אז יהיו שתי הצצות כאלו לפחות שיראו שהאוטומט באותו מצב בדיוק (ב-\( n \) צעדים יש \( n+1 \) “הצצות”: המצב בהתחלה והמצב אחרי כל צעד). אם זיהינו שתי הצצות שבהן האוטומט היה באותו מצב בדיוק, אז אפשר לקחת את כל הריצה בין שתיהן (לא רק את ההצצות בין שתיהן; את כל הריצה) ולשכפל אותה \( i \) פעמים.

אז הנה ניסוח כללי יותר מאשר קודם: אם \( L \) רגולרית אז קיים \( n \) כך שלכל \( z\in L \) ולכל פירוק \( z=uv_{1}v_{2}\dots v_{n}w \) שלה כך ש-\( \left|v_{i}\right|\ge1 \) לכל \( 1\le i\le n \), קיימים זוג אינדקסים \( 0\le k_{1}<k_{2}\le n \) כך ש-\( uv_{1}\dots\left(v_{k_{1}+1}\dots v_{k_{2}}\right)^{i}\dots v_{n}w\in L \) לכל \( i\ge0 \). זו בבירור הכללה של הלמה הרגילה: אם אני בוחר \( u=\varepsilon \) ו-\( v_{i}=z_{i} \) (כלומר, ה-\( v \)-ים הם בדיוק \( n \) האותיות הראשונות ב-\( z \)) אני אקבל את הלמה הרגילה (כאשר מי שאני קורא לו \( v \) בלמה הרגילה יהיו האותיות \( z_{k_{1}}\dots z_{k_{2}} \)).

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

אם \( L \) רגולרית אז קיים \( n \) כך שלכל \( z \) ולכל פירוק \( z=uv_{1}v_{2}\dots v_{n}w \) שלה כך ש-\( \left|v_{i}\right|\ge1 \) לכל \( 1\le i\le n \), קיימים זוג אינדקסים \( 0\le k_{1}<k_{2}\le n \) כך שלכל \( i\ge0 \) מתקיים ש- \( z\in L\iff uv_{1}\dots\left(v_{k_{1}+1}\dots v_{k_{2}}\right)^{i}\dots v_{n}w\in L \).

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

מה שמעניין הוא שהתנאי הזה הוא גם מספיק, כלומר שאם הוא מתקיים, אז \( L \) רגולרית. ולמעשה, אפילו אפשר להחליש אותו קצת ולהתייחס רק למקרה שבו \( i=0 \). כלומר, הנה המשפט שאני רוצה להוכיח:

בהינתן שפה \( L \), אם קיים \( n \) כך שלכל \( z \) ולכל פירוק \( z=uv_{1}v_{2}\dots v_{n}w \) שלה כך ש-\( \left|v_{i}\right|\ge1 \) לכל \( 1\le i\le n \), קיימים זוג אינדקסים \( 0\le k_{1}<k_{2}\le n \) כך שמתקיים \( z\in L\iff uv_{1}\dots v_{k_{1}}v_{k2+1}\dots v_{n}w\in L \), אז \( L \) רגולרית.

כאן \( uv_{1}\dots v_{k_{1}}v_{k2+1}\dots v_{n}w \) זו פשוט דרך קומפקטית לכתוב \( uv_{1}\dots\left(v_{k_{1}+1}\dots v_{k_{2}}\right)^{0}\dots v_{n}w \).

מעכשיו אקרא לדבר הזה “התכונה”. שימו לב שהתכונה הזו תלויה בפרמטר שמאפיין אותה - \( n \). מכאן ואילך גם הוא יהיה קבוע.

למה שהתכונה הזו תהיה שקולה לכך ששפה היא רגולרית? איך בכלל אפשר להראות שהשפה היא רגולרית? נבנה לה אוטומט? ובכן, לא. בואו ניזכר בקריטריון נטול אוטומטים לכך ששפה היא רגולרית: אם משפט מייהיל-נרוד חל עליה. כלומר, אם יש ליחס השקילות \( R_{L} \) רק מספר סופי של מחלקות שקילות, או באופן שקול - אם קיים רק מספר סופי של שפות מהצורה \( u^{-1}L \) (כזכור, \( u^{-1}L\triangleq\left\{ v\in\Sigma^{*}\ |\ uv\in L\right\} \) ).

מה שהתכונה של למת הניפוח נותנת לנו הוא עוד משהו שהוא מעין-סופי שכזה. בניסוח מילולי התכונה אומרת “לכל מילה מאורך גדול מ-\( n \) אפשר למצוא מילה קצרה יותר כך ששתיהן ביחד ב-\( L \) או לא ב-\( L \)”. אם חוזרים על התהליך הזה מספיק פעמים מגיעים אל מילה מאורך לכל היותר \( n \) שגורלה זהה לגורל המילה המקורית שהתחלנו ממנה. זה אומר שהשפה \( L \) שלנו מאופיינת במובן מסויים על פי המילים עד גודל \( n \) ששייכות אליה. אם נצליח להוכיח ששתי שפות שונות \( L_{1},L_{2} \) ששתיהן מקיימות את התכונה עבור אותו קבוע \( n \) לא יכולות להיות מאופיינות על ידי אותה קבוצה של מילים-עד-גודל \( n \), נלמד מזה משהו מעניין מאוד: שיש רק מספר סופי של שפות שמקיימות את התכונה עבור \( n \) (אגב, אני מזהיר מראש שאני משקר כדי לתת לכם אינטואיציה: אלו לא “מילים-עד-גודל \( n \)” אלא “מילים-עד-גודל \( N \) שהוא מספר שונה לגמרי ועוד נבין בהמשך איך מגיעים אליו אבל סבלנות חברים”).

זה מתווה לנו את האסטרטגיה להוכחה: השלב הראשון, הקל, יהיה להוכיח שאם \( L \) מקיימת את התכונה עבור הקבוע \( n \), אז גם \( u^{-1}L \) מקיימת את התכונה עבור אותו קבוע \( n \). השלב השני, הקשה יותר, יהיה להוכיח את מה שדיברתי עליו בפסקה הקודמת. אחרי שנסיים את שני השלבים הללו, משפט מייהיל-נרוד מסיים את העבודה: יש רק מספר סופי של שפות שמקיימות את התכונה עבור \( n \), וכל \( u^{-1}L \) מקיימת את התכונה עבור \( n \), אז יש רק מספר סופי של שפות מהצורה \( u^{-1}L \).

נתחיל עם השלב הקל. אנחנו מניחים ש-\( L \) מקיימת את התכונה עבור \( n \). בואו ניקח \( u\in\Sigma^{*} \) כלשהו ונוכיח שגם \( u^{-1}L \) מקיימת את התכונה. כלומר, ניקח \( z\in u^{-1}L \) ופירוק \( z=xv_{1}v_{2}\dots v_{n}y \) של \( z \). מה שאנחנו צריכים לעשות הוא למצוא זוג אינדקסים כך שאפשר להשמיט את ה-\( v \)-ים שביניהם ולקבל מילה ששקולה ל-\( z \) מבחינת שייכות ל-\( u^{-1}L \).

כעת, מכיוון ש-\( z\in u^{-1}L \), נובע מכך ש-\( uz\in L \). אז אפשר להשתמש בתכונה על \( uz \): ניקח את הפירוק \( z=uxv_{1}\dots v_{n}y \) ונמצא שני אינדקסים עבורו. שימו לב כמה העסק פשוט - את ה-\( u \) שבתחילת המילה אנחנו דוחפים לאיזור של ה”לא מעניין, אין צורך למחוק מכאן דברים”, והכל ממשיך כרגיל. אנחנו מקבלים שקיימים \( k_{1},k_{2} \) כך ש-\( uz\in L\iff uxv_{1}\dots v_{k_{1}}v_{k2+1}\dots v_{n}y\in L \); המסקנה המיידית היא ש-\( z\in u^{-1}L\iff xv_{1}\dots v_{k_{1}}v_{k2+1}\dots v_{n}y\in u^{-1}L \), וזה מה שרצינו להראות. אז זה היה קל.

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

לכל זוג מספרים \( r,s \) טבעיים קיים מספר \( R\left(r,s\right) \) כך שבכל קבוצה עם לפחות \( R\left(r,s\right) \) אנשים שכל זוג מביניהם הם או אויבים או חברים, קיימת קבוצה מגודל \( r \) שכולם בה חברים, או קבוצה מגודל \( s \) שכולם בה אויבים.

לכל זוג מספרים \( r,s \) טבעיים קיים מספר \( R\left(r,s\right) \) כך שבכל גרף מלא עם לפחות \( R\left(r,s\right) \) שקשתותיו צבועות באדום או כחול, קיימת קבוצה של \( r \) צמתים שכל הקשתות ביניהם אדומות, או \( s \) צמתים שכל הקשתות ביניהם כחולות.

לכל זוג מספרים \( r,s \) טבעיים קיים מספר \( R\left(r,s\right) \) כך שבכל גרף עם לפחות \( R\left(r,s\right) \) קודקודים קיים קליק מגודל \( r \) או קבוצה בלתי תלויה מגודל \( s \). זה הניסוח שבו אני אשתמש בהמשך, ואני מקווה שהוא ברור עכשיו (קליק היא קבוצה של צמתים כך שבין כל זוג מביניהם קיימת קשת; קבוצה בלתי תלויה היא קבוצת צמתים כך שלכל זוג מביניהם אין קשת).

יופי, איך זה קשור בכלל?

בואו ניקח את \( N=R\left(n+1,n+1\right) \). אני רוצה לטעון שאם יש לי שתי שפות \( L_{1},L_{2} \), כך ש:

1. \( L_{1},L_{2} \) מקיימות את התכונה עבור \( n \).
2. \( L_{1},L_{2} \) מסכימות על כל המילים עד גודל \( N-1 \), דהיינו \( \left\{ w\in L_{1}\ |\ \left|w\right|\le N-1\right\} =\left\{ w\in L_{2}\ |\ \left|w\right|\le N-1\right\} \).

אז מתקיים \( L_{1}=L_{2} \). זה מסיים את ההוכחה, כי יש רק מספר סופי של קבוצות מילים עד גודל \( N-1 \) (יש בדיוק \( 2^{N-1} \) כאלו).

כלומר, אנחנו רוצים להוכיח ש-\( w\in L_{1}\iff w\in L_{2} \) לכל \( w\in\Sigma^{*} \). ההוכחה תהיה באינדוקציה על האורך של \( w \). הבסיס נתון לנו, עד \( \left|w\right|=N-1 \). לכן אפשר להניח ש-\( \left|w\right|\ge N \). בואו נסמן את \( N-1 \) האותיות הראשונות של \( w \) במפורש: \( w=a_{1}a_{2}\dots a_{N-1}w^{\prime} \). עכשיו אפשר להגדיר את הגרף שעליו נפעיל את משפט רמזי שלנו. הצמתים יהיו פשוט המספרים \( V=\left\{ 0,2,\dots,N-1\right\} \) (ולכן הגרף גדול מספיק כדי שנוכל להפעיל עליו את משפט רמזי). הקשתות יהיו בין זוגות אינדקסים שעבורם התכונה של \( n \) מתקיימת ביחס ל-\( L_{1} \), כלומר

\( E=\left\{ \left(i,j\right)\ |\ 0\le i<j\le N-1,\ a_{1}a_{2}\dots a_{i}a_{j+1}\dots a_{N-1}w^{\prime}\in L_{1}\right\} \)

קרוב לודאי שאתם מרגישים שיש פה חוסר סימטריה מוזר - השתמשתי ב-\( L_{1} \), אבל מה עם \( L_{2} \)? ובכן, שימו לב שהייתי יכול באותה מידה בדיוק להשתמש ב-\( L_{2} \) ולקבל את אותה \( E \), בזכות הנחת האינדוקציה (כי אנחנו כבר משוכנעים ש-\( L_{1},L_{2} \) זהות על כל מילה ארוכה פחות מ-\( w \)).

עכשיו אפשר להשתמש במשפט רמזי. נקבל שקיימת קבוצה \( U \) של \( n+1 \) מספרים \( F=\left\{ i_{0},i_{1},\dots,i_{n}\right\} \), כך שכל זוג מספרים מהקבוצה שייך ל-\( E \), או שכל זוג מספרים מהקבוצה לא שייך ל-\( E \).

כעת סוף סוף אפשר להשתמש בנתון הנוסף שלנו, לפיו \( L_{1},L_{2} \) מקיימות את התכונה עבור \( n \). אנחנו רוצים להשתמש בתכונה עבור \( w \), כמובן, אבל בשביל זה אנחנו קודם כל צריכים להציג פירוק של \( w \): הפירוק יתבסס על קבוצת האינדקסים שמשפט רמזי נתן לנו. נגדיר \( w=xv_{1}v_{2}\dots v_{n}y \) כך ש-\( v_{1}=a_{i_{0}}\dots a_{i_{1}} \) ו-\( v_{2}=a_{i_{1}}\dots a_{i_{2}} \) וכן הלאה עד \( v_{n}=a_{i_{n-1}}\dots a_{i_{n}} \).

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

במקרה הראשון, שבו כל זוג איברים מ-\( U \) מחוברים בקשת, אנחנו יודעים שלכל \( i<j \) כך ש-\( i,j\in U \) נקבל ש-\( xv_{1}v_{2}\dots v_{i}\dots v_{j+1}\dots v_{n}\in L_{1} \) וגם \( xv_{1}v_{2}\dots v_{i}\dots v_{j+1}\dots v_{n}\in L_{2} \). זו בעצם דרך “לסדר” את התכונה - התכונה הרי אומרת רק שקיימים זוג אינדקסים שעבורם אנחנו מקבלים מילה שגורלה זהה לזה של \( w \). עכשיו אנחנו אומרים שהמשחק הזה מכור מראש - לכל זוג אינדקסים שנבחר, התוצאה תהיה תמיד זהה - שייכות לשפה. רואים איך זה מסיים?

עדיין, בואו נכתוב את זה באופן מפורש. מכיוון ש-\( L_{1} \) מקיימת את התכונה, קיימים \( k_{1},k_{2} \) כך ש-\( w\in L_{1}\iff xv_{1}\dots v_{k_{1}}\dots v_{k_{2}+1}\dots v_{n}\in L_{1} \). מכיוון שאגף ימין מתקיים, אנחנו מקבלים ש-\( w\in L_{1} \). באותו אופן בדיוק, מכיוון ש-\( L_{2} \) מקיימת את התכונה, קיימים \( t_{1},t_{2} \) (אולי שונים מ-\( k_{1},k_{2} \) - כל הפואנטה היא שזה לא משנה, בשביל זה היינו צריכים את רמזי) כך ש-\( w\in L_{2}\iff xv_{1}\dots v_{t_{1}}\dots v_{t_{2}+1}\dots v_{n}\in L_{2} \), וקיבלנו שגם \( w\in L_{2} \). המקרה השני של משפט רמזי הוא אותו הדבר, רק שנקבל הפעם ש-\( w\notin L_{1} \) וגם \( w\notin L_{2} \). סך הכל קיבלנו את מה שרצינו: \( w\in L_{1}\iff w\in L_{2} \). זה מסיים את ההוכחה.

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