משפט קלייני - הוכחה נוספת

אולי המשפט המרכזי בסדרת הפוסטים שלי על שפות רגולריות היה משפט קלייני. כזכור, שפה רגולרית היא שפה שקיים אוטומט סופי דטרמיניסטי שמקבל אותה, אבל משפט קלייני נתן אפיון שונה לגמרי עבורה, שאפשר לנו להבין מה המבנה הכללי של אוסף השפות הרגולריות. כזכור, הוא אמר שהשפות הרגולריות הן בדיוק השפות שמתקבלות על ידי פעולות האיחוד, השרשור וסגור-קלייני (“הפעולות הרגולריות”), מתוך אוסף בסיס של שפות שכלל את השפה הריקה, השפה שהמילה היחידה בה היא המילה הריקה, ולכל אות \( \sigma\in\Sigma \), השפה \( \left\{ \sigma\right\} \).

ההוכחה הייתה נפלאה, לטעמי. הרעיון היה להתחיל מאוטומט \( A \) ולהגדיר שפות שאיכשהו ממדלות חישובים ב-\( A \): השפה \( L_{i,j}^{k} \) תיארה את כל המילים שמעבירות את האוטומט מהמצב \( q_{i} \) למצב \( q_{j} \) בלי לעבור במצב עם אינדקס גדול מ-\( k \) בתוך החישוב הזה. את השפות הללו היה ניתן לתאר בצורה רקורסיבית באמצעות הפעולות הרגולריות, כשתנאי הבסיס של הרקורסיה היו שפות פשוטות במיוחד שמתקבלות משפות הבסיס על ידי פעולות רגולריות.

עכשיו אני רוצה לתת הוכחה קצת שונה.

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

ובכן, כי זה מגניב.

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

לאוטומט רגיל יש פונקציית מעברים שמקבלת את המצב הנוכחי ואות מ-\( \Sigma \), ומחזירה את המצב שעוברים עליו. מבחינה רעיונית, אנחנו “אוכלים” את האות הזו מהקצה הימני של הקלט תוך כדי ביצוע המעבר. כבר ראינו הרחבה של המודל הרגיל שבו את האות מ-\( \Sigma \) מחליפה המילה הריקה, ואז האינטואיטיציה הייתה שביצענו מעבר אבל לא אכלנו כלום מהקלט. אם כן, בואו ניקח את הרעיון הזה צעד אחד קדימה ונגדיר פונקציית מעברים שיכולה לקבל כל מילה שהיא: \( \delta:Q\times\Sigma^{*}\to2^{Q} \). שימו לב שאני מצהיר מראש שהפונקציה הזו מתארת אוטומט אי דטרמיניסטי: עבור זוג של מצב ומילה, ייתכן שעוברים ליותר ממצב אחד, וייתכן גם שלא עוברים לשום מצב עבורה.

איך נראה “חישוב” באוטומט כזה? ובכן, זה לא כזה מסובך: בכל צעד חישוב “מנחשים” מילה \( w \) כלשהי שהיא רישא של הקלט הנוכחי, “אוכלים” אותה מהקלט, ועוברים למצב כלשהו מתוך \( \delta\left(q,w\right) \), כאשר \( q \) הוא המצב הנוכחי. להגדיר את פונקציית המעברים המורחבת מבחינה פורמלית זה עניין קצת מעצבן ולא ניכנס אליו - תחת זאת, בואו נראה עוד דרך לחשוב על האוטומט הזה.

בתיאור הרגיל של אוטומט, אנחנו מציירים אותו בתור גרף שבו הצמתים הם מצבי האוטומט, ויש קשת ממצב אחד לאחר עם סימונים שהם האותיות שמעבירות את המצב הראשון לשני. בהכללה שלי אפשר לחשוב שיש קשת בין כל זוג מצבים (וגם בין מצב לעצמו), ולכל קשת כזו יש סימון שהוא שפה (שיכולה להיות גם השפה הריקה, למשל, ובמצב הזה אני אתייחס לכך כאילו פשוט אין קשת). פורמלית, לכל זוג מצבים \( q_{i},q_{j} \) קיימת שפה \( L_{ij}\subseteq\Sigma^{*} \) שמכילה את כל המילים שמעבירות בצעד יחיד את \( q_{i} \) אל \( q_{j} \): \( L_{ij}=\left\{ w\in\Sigma^{*}\ |\ q_{j}\in\delta\left(q_{i},w\right)\right\} \). אפשר להגדיר את השפה שהאוטומט מקבל בצורה הבאה: לכל מסלול \( q_{i_{1}}\to q_{i_{2}}\to\dots\to q_{i_{k}} \) כך שהמצב הראשון בו הוא התחלתי והמצב האחרון בו הוא מקבל, נסתכל על השרשור \( L_{i_{1}i_{2}}L_{i_{2}i_{3}}\cdots L_{i_{k-1}i_{k}} \). נאחד את כל השרשורים הללו, לכל (אולי אינסוף) המסלולים ממצב התחלתי למצב מקבל - קיבלנו את שפת האוטומט.

המודל הזה כמובן חזק בצורה פסיכית. כל שפה \( L \) ניתן לקבל על ידי אוטומט טריוויאלי לגמרי, עם מצב התחלתי \( q_{0} \), מצב מקבל יחיד \( q_{f} \), ומעבר \( \delta\left(q_{0},L\right)=q_{f} \). למעשה, זו הפואנטה - בגישת “צמצום האוטומט” שתיארתי קודם, אנחנו נתחיל מאוטומט כללי ונצטמצם בסוף לאוטומט טריוויאלי שכזה. עדיין, אם המודל חזק כל כך, מה הטעם בו? מה למדנו ממנו?

ובכן, זה פשוט. הנה הגרסה המורחבת של קלייני: השפה שמתקבלת על ידי אוטומט נתון כלשהו מהמודל הזה נמצאת בקבוצה האינדוקטיבית שנוצרת על ידי הפעולות הרגולריות, כשקבוצת שפות הבסיס כוללת בדיוק את השפות \( L_{ij} \) עבור האוטומט הזה. למה זו גרסה מורחבת של קלייני? כי כל אוטומט סופי רגיל הוא כזה שהשפות \( L_{ij} \) שלו כוללות לכל היותר את כל השפות מהצורה \( \left\{ \sigma\right\} \), את השפה \( \left\{ \varepsilon\right\} \) (למשל, במעבר ממצב לעצמו, או אם יש לנו מסעי-\( \varepsilon \)) ואת השפה \( \emptyset \) (כשיש זוג מצבים שאין בכלל מעבר מהראשון אל השני), ואיחודים שלהן (למשל, אם \( \delta\left(q,a\right)=p \) וגם \( \delta\left(q,b\right)=p \) ואלו המעברים היחידים שמעבירים את \( q \) אל \( p \) אז נקבל ש-\( L_{qp}=\left\{ a,b\right\} \)). זה בדיוק הבסיס שלנו במשפט קלייני ה”רגיל”.

נעבור להוכחת המשפט עצמו. בואו ניקח אוטומט מוכלל \( A \) כלשהו. נסמן את מצביו ב-\( Q=\left\{ q_{1},q_{2},\dots,q_{n}\right\} \). נוסיף שני מצבים מיוחדים \( q_{s},q_{f} \) כך ש-\( q_{s} \) יהיה המצב ההתחלתי היחיד, \( q_{f} \) יהיה המצב המקבל היחיד, ויהיה מעבר-\( \varepsilon \) מ-\( q_{s} \) לכל מצב התחלתי ב-\( A \) ומכל מצב מקבל ב-\( A \) ל-\( q_{f} \). הרעיון עכשיו יהיה להעיף באופן סדרתי את הצמתים \( q_{1},q_{2},\dots,q_{n} \) מהאוטומט, כך שאחרי כל העפה אנחנו מתקנים את הסימונים על הקשתות שנותרו באוטומט בצורה שמבטיחה שנקבל אוטומט שקול (כלומר, שמקבל את אותה שפה). אחרי שנעיף את כל הצמתים הללו נישאר רק עם \( q_{s},q_{f} \), והקשת מ-\( q_{s} \) אל \( q_{f} \) תקודד בדיוק את השפה שלנו (שאר הקשתות בגרף לא ישפיעו; הקשת מ-\( q_{f} \) אל \( q_{s} \) היא עם הסימון \( \emptyset \) והקשתות מהצמתים לעצמם הן עם הסימון \( \left\{ \varepsilon\right\} \)). לכן כל מה שאנחנו צריכים לעשות כדי להוכיח את המשפט הוא להראות איך כל “תיקון סימוני קשתות” ניתן לביצוע עם הסימונים הנוכחיים שעל הקשתות והפעולות הרגולריות. כאן זה כבר תרגיל נחמד שאפשר לתת לסטודנטים לאוטומטים והם יצליחו לפתור בעצמם; אבל בואו נעשה אותו במפורש. כפי שתראו, זה מאוד מזכיר את הבניה שבה השתמשנו בהוכחת משפט קלייני המקורי.

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

בואו ניקח שני צמתים כאלו: צומת \( q_{j} \) כך שיש קשת \( q_{j}\to q_{i} \), וצומת \( q_{k} \) כך שיש קשת \( q_{i}\to q_{k} \) (זכרו שאצלנו בעצם יש קשת מכל צומת לכל צומת, אבל היא עשויה להיות מסומנת בשפה הריקה ואם תבדקו, תראו שזה שקול לכך שלא תהיה קשת). אנחנו רוצים “להוסיף” קשת מ-\( q_{j} \) אל \( q_{k} \), אבל כמובן שאולי כבר יש כזו - השפה \( L_{jk} \) מתארת את הסימון שלה. אז אנחנו רוצים לבנות \( L_{jk}^{\prime} \) “מתוקנת”.

מה השפה המתוקנת צריכה לכלול? את כל המילים שמעבירות את \( q_{j} \) אל \( q_{k} \) באופן ישיר, כלומר את \( L_{jk} \), וכמו כן את כל המילים שמעבירות את \( q_{j} \) אל \( q_{k} \) באמצעות שימוש במצב הביניים \( q_{i} \). נאיבית אפשר לחשוב שהמילים הללו הן בדיוק \( L_{ji}\cdot L_{ik} \), כלומר שרשור של מילה שמעבירה אותנו מ-\( q_{j} \) אל \( q_{i} \) ואז מ-\( q_{i} \) אל \( q_{k} \); אבל זכרו שאנחנו עשויים להישאר ב-\( q_{i} \) במשך מספר צעדים שבהם נלך מ-\( q_{i} \) אל עצמה. מכאן שהשפה היא \( L_{ji}\cdot L_{ii}^{*}\cdot L_{ik} \), וקיבלנו ש-\( L_{jk}^{\prime}=L_{jk}\cup L_{ji}\cdot L_{ii}^{*}\cdot L_{ik} \). זה מסיים את ההוכחה, ובצורה מאוד נחמדה - אנחנו רואים בדיוק איך כל שלוש הפעולות הרגולריות באות לידי ביטוי באותה משוואה.

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

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