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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com