משפט מייהיל-נרוד – נקודת מבט נוספת, ואלגוריתמי מינימיזציה

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

נתחיל בתזכורת מה הולך במשפט מייהיל-נרוד. בהינתן שפה $latex L$ כלשהי מעל $latex \Sigma^{*}$, הגדרנו יחס שקילות $latex R_{L}$ מעל $latex \Sigma^{*}$: $latex xR_{L}y$ אם ורק אם לא קיימת "סיפא מפרידה" של $latex x,y$ ביחס ל-$latex L$, כלומר לכל $latex z\in\Sigma^{*}$ מתקיים $latex xz\in L\iff yz\in L$. סימנו את אוסף מחלקות השקילות של היחס הזה ב-$latex \Sigma^{*}/R_{L}$, והמשפט אמר ש-$latex L$ רגולרית אם ורק אם מספר מחלקות השקילות של היחס הוא סופי. האינטואיציה היא שניתן לבנות אוטומט (לאו דווקא סופי) עבור $latex L$ שמצביו הם בדיוק $latex \Sigma^{*}/R_{L}$, המצב ההתחלתי שלו הוא $latex \left[\varepsilon\right]$ (מחלקת השקילות של $latex \varepsilon$), מצביו המקבלים הם מהצורה $latex \left[w\right]$ עבור כל $latex w\in L$, ופונקציית המעברים שלו היא $latex \delta\left(\left[w\right],\sigma\right)=\left[w\sigma\right]$. הוכחנו שהאוטומט הזה הוא בעל מספר המצבים המינימלי מבין כל האוטומטים עבור $latex L$, ולכן $latex L$ הייתה רגולרית אם ורק אם המספר המינימלי הזה היה סופי.

עכשיו בואו נתאר את כל העסק הזה מזווית ראייה אחרת. אני הולך להשתמש במושג שהזכרתי קודם אבל לא קיבל עד כה את הזרקור שמגיע לו – המושג של חלוקה של שפות. נתחיל הפעם דווקא עם חלוקה במילה בודדת, ועם סימון חדש כדי להציג את זה. אם $latex w=uv$ היא מילה ש-$latex u$ היא רישא שלה, אז אסמן $latex u^{-1}w\triangleq v$. כלומר, $latex u^{-1}w$ היא מה שמקבלים מ-$latex w$ אחרי שמסלקים ממנו את הרישא $latex u$. האינטואיציה לסימון הזה עם החזקה של המינוס 1 מגיעה מתורת החבורות, ולא אכביר עליה מילים. צריך להיזהר קצת עם הסימון – אם $latex u$ איננה רישא של $latex w$, אז אין שום משמעות לסימון $latex u^{-1}w$ בהקשר שלנו. כמו כן, באופן דומה אפשר גם להגדיר $latex wu^{-1}$ אבל לא אזדקק לסימון הזה ולכן לא אציג אותו בהמשך.

עכשיו, אם $latex L$ היא שפה כלשהו, אפשר להכליל את פעולת החלוקה עבורה: להגדיר $latex u^{-1}L\triangleq\left\{ u^{-1}w\ |\ w\in L\right\} $, כאשר המוסכמה כאן היא שאם $latex u^{-1}w$ אינו מוגדר הוא אינו משתתף בקבוצה (מבחינה פורמלית הסימון שלי לא תקין והייתי צריך להוסיף במפורש את התנאי ש-$latex u$ היא רישא של $latex w$, אבל אני בכוונה משתמש פה בסימון לא תקין – מה שנקרא Abuse of notation – כי חשוב לי להדגיש שככה זה עובד במתמטיקה – יותר חשובה לנו נוחות הסימון כל עוד כולם מבינים את הכוונה, מאשר נוקדנות ברמת הסימונים). גם את זה אפשר להכליל ולקבל חלוקה משמאל של שפות כדי שהגדרתי אותה פעם: $latex L_{2}^{-1}L_{1}\triangleq\left\{ u^{-1}w\ |\ u\in L_{2},\in L_{1}\right\} $, אבל לא אזדקק לסימון הזה יותר מדי הפעם.

עכשיו אפשר לנסח את משפט מייהיל-נרוד בטרמינולוגיה החדשה שלנו: שפה $latex L$ היא רגולרית אם ורק אם הקבוצה $latex \left\{ u^{-1}L\ |\ u\in\Sigma^{*}\right\} $ סופית; וגודל הקבוצה שווה למספר המצבים באוטומט סופי דטרמיניסטי מינימלי עבור $latex L$.

במבט ראשון אולי לא ברור מה הקשר, אבל במבט שני די ברור שזה בדיוק אותו דבר: דרך אחרת ושקולה לנסח את הטענה ש-$latex xR_{L}y$ היא לומר ש-$latex x^{-1}L=y^{-1}L$ – כלומר, שאוסף כל המילים $latex z$ כך ש-$latex xz\in L$ שווה לאוסף כל המילים כך ש-$latex yz\in L$. אז עד כה לא עשיתי כלום חוץ מאשר הצבעה על העובדה (הנחמדה) שאפשר לנסח את המשפט בעזרת מושג החלוקה, במקום להזדקק למחלקות שקילות.

עכשיו בואו נכניס אוטומטים לתמונה. ניקח אוטומט סופי דטרמיניסטי כלשהו $latex A=\left(Q,\Sigma,q_{0},\delta,F\right)$. עכשיו, לכל מצב $latex q\in Q$ בואו נסמן ב-$latex L_{q}$ את שפת כל המילים שאם אנחנו נמצאים ב-$latex q$ וקוראים אותן, נגיע למצב מקבל: $latex L_{q}\triangleq\left\{ w\in\Sigma^{*}\ |\ \hat{\delta}\left(q,w\right)\in F\right\} $. בבירור $latex L\left(A\right)=L_{q_{0}}$ (אם זה לא ברור נסו להסביר לעצמכם את ההגדרה). עכשיו, לפני שנמשיך, אני רוצה להציג סימון שיחסוך לי את הצורך לכתוב $latex \hat{\delta}$ עם סוגריים כל הזמן: במקום לכתוב $latex \hat{\delta}\left(q,w\right)$ אני אכתוב $latex q\cdot w$. פורמלית, אפשר לחשוב על זה כאילו $latex w$ פועלת על $latex q$, למי שמכיר את המושג הזה (כאן זו פעולה של המונואיד $latex \Sigma^{*}$ על הקבוצה $latex Q$, למי שמכיר את ההגדרות). התכונה שמעניינת אותנו כאן היא ש-$latex q\cdot\left(uv\right)=\left(q\cdot u\right)\cdot v$ (מה שהוכחתי בעבר בתור $latex \hat{\delta}\left(q_{0},uv\right)=\hat{\delta}\left(\hat{\delta}\left(q_{0},u\right),v\right)$) ובגללה בחרתי את הסימון בצורה שבה בחרתי (נראה לי בהתחלה יותר טבעי לסמן $latex w\cdot q$, אבל אני רוצה להימנע מזוועות כמו $latex \left(uv\right)\cdot q=v\cdot\left(u\cdot q\right)$). בסימון הזה, $latex L_{q}\triangleq\left\{ w\in\Sigma^{*}\ |\ q\cdot w\in F\right\} $

בואו נניח שכל המצבים ב-$latex A$ ישיגים (לאוטומט כזה אקרא נגיש), כי קל להעיף מאוטומט מצבים לא ישיגים ומקבלים אוטומט שקול. זה אומר שלכל $latex q$ קיימת מילה $latex u$ כך ש-$latex q=q_{0}\cdot u$. אני טוען ש-$latex L_{q}=u^{-1}L$, ודי קל לראות את זה: $latex w\in u^{-1}L$ אם ורק אם $latex uw\in L$, אם ורק אם $latex q_{0}\cdot uw\in F$, אם ורק אם $latex \left(q_{0}\cdot u\right)\cdot w=q\cdot w\in F$, אם ורק אם $latex w\in L_{q}$. באופן דומה, אם $latex q=q_{0}\cdot v$ עבור $latex v\ne u$ אז נקבל ש-$latex L_{q}=v^{-1}L$ ולכן בפרט $latex u^{-1}L=v^{-1}L$. המסקנה היא שהפונקציה $latex f\left(q\right)=L_{q}$ היא פונקציה מ-$latex Q$ על הקבוצה $latex \left\{ u^{-1}L\ |\ u\in\Sigma^{*}\right\} $, כלומר הגודל של $latex Q$ הוא לפחות כגודל הקבוצה הזו, ומכאן שמספר המצבים באוטומט שבונים בהוכחת מייהיל-נרוד הוא אכן מינימלי (כי מספר מצביו שווה לגודל הקבוצה $latex \left\{ u^{-1}L\ |\ u\in\Sigma^{*}\right\} $).

עכשיו, נניח שיש לנו שני מצבים $latex q,p$ כך ש-$latex L_{q}=L_{p}$. מה זה אומר? זה אומר ששני חישובים, שאחד מהם הגיע אל $latex q$ והשני הגיע אל $latex p$, יהיו משם והלאה שקולים במובן מסויים; אם נמשיך את שני החישובים על אותה מילה, או ששניהם יסתיימו בקבלה או ששניהם יסתיימו בדחיה (אבל זה ממש לא אומר שהחישובים יגיעו לאותם מצבים – ייתכן שלא יהיו להם מצבים משותפים בכלל). אינטואיטיבית זה אומר שאין לנו צורך בשני מצבים שונים עבור $latex q,p$; אם החישוב מכאן והלאה הוא אותו הדבר, למה לא לאחד את שניהם למצב אחד?

בואו נחדד את מה שאני עושה. אגדיר יחס שקילות $latex \equiv$ על $latex Q$ באופן הבא: $latex q\equiv p$ אם ורק אם $latex L_{q}=L_{p}$. די קל לראות שזה יחס שקילות (כל יחס על קבוצה $latex A$ שמוגדר באמצעות פונקציה $latex f:A\to B$ כלשהי כך ש-$latex a\equiv a^{\prime}$ אם ורק אם $latex f\left(a\right)=f\left(a^{\prime}\right)$ הוא יחס שקילות). כעת אני טוען שקבוצת המנה $latex Q/\equiv$ איזומורפית לקבוצת המנה $latex \Sigma^{*}/R_{L}$, כאשר האיזומורפיזם נתון על ידי $latex \left[w\right]_{R_{L}}\mapsto\left[q_{0}\cdot w\right]_{\equiv}$. להוכיח את זה – זה קצת סיפור. צריך להוכיח שהאיזומורפיזם הזה הוא באמת פונקציה; ושהיא חח"ע ועל.

כדי להוכיח שזו פונקציה צריך להוכיח שאין בהגדרה שלה תלות בנציג, כלומר שאם $latex uR_{L}v$ אז $latex q_{0}\cdot u\equiv q_{0}\cdot v$, כלומר ש-$latex L_{q_{0}\cdot u}=L_{q_{0}\cdot v}$. נניח בשלילה שקיים $latex z$ כך ש-$latex z\in L_{q_{0}\cdot u}$ אבל $latex z\notin L_{q_{0}\cdot v}$, אז $latex \left(q_{0}\cdot u\right)\cdot z\in F$, כלומר $latex uz\in L$, אבל $latex vz\notin L$, בסתירה לכך ש-$latex uR_{L}v$.

כדי להוכיח שהפונקציה היא חח"ע צריך להוכיח את הכיוון ההפוך – שאם $latex L_{q_{0}\cdot u}=L_{q_{0}\cdot v}$ אז $latex uR_{L}v$ – זה פשוט היפוך של הטיעון שנתתי קודם.

כדי להראות שהפונקציה היא על, ניקח מחלקת שקילות $latex \left[q\right]_{\equiv}$ כלשהי. מכיוון שהנחתי שכל מצבי האוטומט ישיגים (בדיוק בשביל השלב הזה) הרי שקיים $latex w$ כך ש-$latex q=q_{0}\cdot w$, ולכן $latex \left[w\right]_{R_{L}}$ הוא מקור של $latex \left[q\right]_{\equiv}$, וסיימנו.

המסקנה היא שכדי לחשב את האוטומט המינימלי, מספיק לנו למצוא את מחלקות השקילות של $latex \equiv$. אחרי שעשינו זאת, עדיין צריך להסביר מה יהיה המצב ההתחלתי שלנו, מי יהיו המצבים המקבלים ומה תהיה פונקציית המעברים. נלך על פי האיזומורפיזם שהצעתי: המצב ההתחלתי יהיה התמונה של $latex \left[\varepsilon\right]_{R_{L}}$, כלומר $latex \left[q_{0}\right]_{\equiv}$; התמונה של כל מצב מקבל $latex \left[w\right]_{R_{L}}$ (כאשר $latex w\in L$) תהיה $latex \left[q_{0}\cdot w\right]_{\equiv}$, ואנחנו יודעים ש-$latex q_{0}\cdot w\in F$, כלומר המצבים המקבלים באוטומט שלנו יהיו מחלקות השקילות של מצבים מקבלים ב-$latex Q$; ופונקציית המעברים תוגדר בתור $latex \delta\left(\left[q\right]_{\equiv},\sigma\right)=\left[q\cdot\sigma\right]_{\equiv}$. זה נותן לנו את האוטומט האופטימלי של מייהיל-נרוד. כל מה שנשאר להסביר הוא איך מוצאים את מחלקות השקילות של $latex \equiv$.

הדרך שבה אעשה זאת היא איטרטיבית – אני אתחיל מיחס שקילות שגוי, שהוא גס מדי – כלומר, כל מי שאמור להיות שקול אכן שקול, אבל יש גם איברים לא שקולים ב-$latex \equiv$ שיהיו שקולים ביחס שלי. לאט לאט אני אלך ואעדן את היחס – כלומר, אם שני איברים לא היו שקולים, הם ימשיכו להיות כאלו, אבל בכל איטרציה אני אקח כמה איברים שהיו שקולים קודם ואפריד אותם זה מזה. נמשיך לבצע את זה עד שנגיע לאיטרציה שבה היחס לא השתנה, ואני אטען שאז הגעתי אל $latex \equiv$. פורמלית, אבנה סדרה של יחסי שקילות $latex \mathcal{Q}_{0},\mathcal{Q}_{1},\dots$ עד שאגיע למצב שבו $latex \mathcal{Q}_{k}=\mathcal{Q}_{k+1}$, והטענה תהיה שאז $latex \mathcal{Q}_{k}$ הוא בדיוק $latex \equiv$, כלומר ש-$latex q\mathcal{Q}_{k}p$ אם ורק אם $latex L_{q}=L_{p}$.

הנה הצעה לגבי האופן שבו כדאי לאתחל:$latex \mathcal{Q}_{0}=\left\{ Q\right\} $ (אני מתאר כאן את יחס השקילות בתור חלוקה של $latex Q$), כלומר כל האיברים יהיו שקולים זה לזה. מכאן והלאה אנחנו "מתקנים" כשאנחנו מוצאים דוגמאות נגדיות לכך שזוגות של מצבים הם שקולים. הדוגמה הנגדית הראשונה היא $latex \varepsilon$. מן הסתם היא מפרידה בדיוק את אותם מצבים שהם מקבלים מאלו שאינם מקבלים (למה?) ולכן יותר הגיוני לאתחל $latex \mathcal{Q}_{0}=\left\{ Q\backslash F,F\right\} $ במקום לאתחל עם קבוצה אחת. מכאן והלאה נפעל איטרטיבית: בהינתן $latex \mathcal{Q}_{k}$ נחשב מתוכה את $latex \mathcal{Q}_{k+1}$ שהיא קצת יותר מדוייקת מ-$latex \mathcal{Q}_{k}$, עד שנגיע למצב שבו אין יותר שינויים.

עכשיו, בהינתן $latex p,q$ שהם שקולים ב-$latex \mathcal{Q}_{k}$, אני אבדוק אם קיים $latex a$ כך ש-$latex q\cdot a,p\cdot a$ לא שקולים ש-$latex \mathcal{Q}_{k}$. אם קיים כזה, אני מפריד את $latex p,q$ ב-$latex \mathcal{Q}_{k+1}$. אם $latex p,q$ היו שקולים ב-$latex \mathcal{Q}_{k}$ ולא מצאתי $latex a$ מפריד שכזה, אני ממשך לסמן אותם כשקולים. הניסוח המילולי הזה מסתיר מאחוריו סכנה כלשהי לסיטואציה לא מוגדרת היטב – שיהיו לי שלושה מצבים $latex p,q,r$ כך ש-$latex p,q$ אמורים להיות לא שקולים אבל $latex p,r$ אמורים להיות שקולים וגם $latex q,r$ אמורים להיות שקולים. אם זה מטריד אתכם קחו רגע כדי להוכיח שזה לא יכול לקרות, ולכן אנחנו מקבלים שגם $latex \mathcal{Q}_{k+1}$ הוא יחס שקילות, וכזה שמעדן את $latex \mathcal{Q}_{k}$. מכיוון שאלו יחס שקילות על קבוצה סופית וכל אחד מהם מעדן את קודמו, מתישהו בהכרח נגיע לנקודת שבת – $latex \mathcal{Q}_{k}=\mathcal{Q}_{k+1}$, מה שמוכיח שהאלגוריתם תמיד מסתיים. נותר להוכיח שהתוצאה היא אכן יחס השקילות שאנחנו רוצים.

כיוון אחד קל. נוכיח באינדוקציה על $latex t$ שאם עבור זוג מצבים כלשהו $latex p,q$ מתקיים ש-$latex L_{p}=L_{q}$ אז $latex q\mathcal{Q}_{t}p$. עבור $latex t=0$ זה בבירור עובד, כי אם $latex q$ לא שקול ל-$latex p$ ב-$latex \mathcal{Q}_{0}$ אז בלי הגבלת הכלליות $latex p\in F$ ו-$latex q\notin F$, מה שאומר ש-$latex \varepsilon\in L_{p}$ אבל $latex \varepsilon\notin L_{q}$. כעת, נניח שזה עובד עבור $latex t$ ונוכיח ל-$latex t+1$: אם $latex L_{p}=L_{q}$ אבל $latex p,q$ לא שקולים ב-$latex \mathcal{Q}_{t+1}$. הנחת האינדוקציה שלנו אומרת ש-$latex p,q$ כן היו שקולים ב-$latex \mathcal{Q}_{t}$, ולכן על פי אופן פעולת האלגוריתם, זה אומר שקיים $latex a$ כך ש-$latex p\cdot a$ ו-$latex q\cdot a$ לא שקולים ב-$latex \mathcal{Q}_{t}$; מכאן שבהכרח $latex L_{q\cdot a}\ne L_{p\cdot a}$ (למה?). בלי הגבלת הכלליות נובע מכך שקיים $latex z$ כך ש-$latex z\in L_{q\cdot a}$ אבל $latex z\notin L_{p\cdot a}$ – מכאן נובע ש-$latex az\in L_{q}$ אבל $latex az\notin L_{p}$, בסתירה לכך ש-$latex L_{q}=L_{p}$, מה שמסיים את הכיוון הזה.

בכיוון השני, אני רוצה להוכיח שאם $latex p\mathcal{Q}_{k}q$ אז $latex L_{p}=L_{q}$. נניח שזה לא המצב, אז תהיה לי לפחות דוגמה נגדית אחת. דוגמה נגדית מורכבת משלושה דברים: זוג מצבים $latex p,q$ כך ש-$latex p\mathcal{Q}_{k}q$, וכמו כן מילה $latex z$ כך ש-$latex z\in L_{p}$ אבל $latex z\notin L_{q}$. כדי שההוכחה תעבוד, אני לא סתם אסתכל על דוגמה נגדית אקראית, אלא אקח כזו שבה $latex z$ הוא הקצר ביותר האפשרי – כלומר, שכל מילה קצרה יותר מ-$latex z$ לא מופיעה באף דוגמה נגדית.

עכשיו אפשר לפרק את $latex z$ באופן הבא: $latex z=az^{\prime}$ (אני מניח ש-$latex z$ הוא מאורך לפחות 1 – למה זה אפשרי?). נקבל ש-$latex z^{\prime}\in L_{p\cdot a}$ אבל $latex z^{\prime}\notin L_{q\cdot a}$. אני חותר לכך שזו סתירה למינימליות של האורך של $latex z$; לצורך כך צריך להשתכנע שהשלשה $latex p\cdot a,q\cdot a$ו-$latex z^{\prime}$ גם היא דוגמה נגדית, כלומר ש-$latex p\cdot a\mathcal{Q}_{k}q\cdot a$. הסיבה שזה נכון היא שאם לא היה מתקיים ש-$latex p\cdot a\mathcal{Q}_{k}q\cdot a$ אז האלגוריתם שלנו היה מפריד את $latex p,q$ ב-$latex \mathcal{Q}_{k+1}$ ובוודאי שלא היינו מקבלים $latex \mathcal{Q}_{k}=\mathcal{Q}_{k+1}$. זה מסיים את הוכחת הנכונות של האלגוריתם. עכשיו לכו לתכנת אותו!

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

כדי שנוכל לתאר את האלגוריתם בצורה פשוטה, כמה סימונים חדשים. נסמן ב-$latex A$ אוטומט סופי כלשהו (לאו דווקא דטרמיניסטי, אבל בלי מסעי-$latex \varepsilon$). נסמן ב-$latex A_{\mbox{det}}$ את הדטרמיניזציה של $latex A$ – האוטומט שמתקבל מאוטומט החזקה של $latex A$ על ידי הסרת מצבים לא ישיגים (אסביר את זה בפירוט בהמשך). נסמן ב-$latex A^{R}$ את ההיפוך של $latex A$ – אוטומט שמתקבל מ-$latex A$ על ידי היפוך כל כיווני הקשתות והחלפת תפקידי המצבים ההתחלתיים והמקבלים (כזכור, $latex L\left(A^{R}\right)=\left(L\left(A\right)\right)^{R}$ כאשר $latex L^{R}$ היא היפוך כל המילים ב-$latex L$), ונסמן ב-$latex A_{\mbox{min}}$ את האוטומט הדטרמיניסטי המינימלי ששקול ל-$latex A$. אז אני טוען שמתקיים:

$latex A_{\mbox{min}}=\left(\left(\left(A^{R}\right)_{\mbox{det}}\right)^{R}\right)_{\mbox{det}}$

במילים: כדי לקבל את האוטומט הדטרמיניסטי המינימלי ששקול ל-$latex A$, פעלו כך: קודם כל הפכו את $latex A$. בצעו דטרמיניזציה לתוצאה. הפכו את התוצאה ובצעו למה שקיבלתם דטרמיניזציה. הופס! קיבלתם את האוטומט המינימלי.

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

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

באופן הזה, הרבה פעמים אנחנו מקבלים מצבים מיותרים. דוגמה טריוויאלית היא מה שנקבל אם נבצע את הבניה הזו על אוטומט שהוא כבר דטרמיניסטי, המצבים היחידים שנזדקק להם בפועל הם קבוצות שהן סינגלטונים (למה?). כל שאר המצבים פשוט יהיו לא ישיגים מהמצב ההתחלתי. אז כשרוצים לבצע דטרמיניזציה בפועל של אוטומט, לא מתחילים מבניה של כל המצבים האפשריים (יש המון כאלו – 2 בחזקת מספר המצבים של האוטומט המקורי). פשוט מבצעים DFS מהמצב ההתחלתי, שהוא $latex \left\{ q_{0}\right\} $. לכל אות מחשבים לאיזה מצב של אוטומט החזקה עוברים ממנו, ולכל מצב כזה מבצעים את אותו חישוב, וכדומה. התוצאה עשויה להיות אוטומט החזקה המלא, במקרה שבו כל המצבים שלו הם ישיגים; אבל לרוב היא תהיה הרבה יותר קטנה ולכן העניין הזה פרקטי בפועל. כאמור, אם $latex A$ הוא אוטומט, אז אסמן ב-$latex A_{\mbox{det}}$ את הדטרמיניזציה הזו שלו.

כדי לקבל אינטואיציה כלשהי לכך שזה עובד, בואו נראה דוגמת צעצוע. אני אקח אוטומט עבור שפת כל המילים מאורך אי-זוגי מעל $latex \left\{ a,b\right\} $ ובכוונה האוטומט הזה יהיה לא מינימלי – במקום שני מצבים יהיו לו שלושה, כשבבירור אפשר לאחד את המצב הראשון והשלישי:

diagram005

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

diagram006

ועכשיו אני מבצע דטרמיניזציה:

diagram007הופס! קיבלנו רק שני מצבים במקום שלושה – איכשהו הדטרמיניזציה זיהתה ש-$latex q_{0},q_{2}$ הם אותו הדבר מבחינתנו והם נדחסו למצב יחיד. למעשה, מה שקיבלנו הוא כבר אוטומט עבור השפה שלנו – לא צריך את ההיפוך והדטרמיניזציה הנוספים, והם גם לא משנים את האוטומט כלל (למה?).

כדי להבין למה כאן הספיק לנו רק "חצי" מהאלגוריתם, הנה המשפט הכללי שעליו אני מסתמך באלגוריתם. לפני כן, הגדרה אחרונה: נאמר שאוטומט $latex A$ הוא קו-בלהבלה, כאשר במקום "בלהבלה" קחו את התכונה החביבה עליכם, אם $latex A^{R}$ מקיים את בלהבלה. למשל, $latex A$ הוא קו-דטרמיניסטי אם $latex A^{R}$ הוא דטרמיניסטי; והוא קו-נגיש אם $latex A^{R}$ נגיש, כלומר כל מצבי $latex A^{R}$ ישיגים. הנה המשפט: אם $latex A$ הוא קו-דטרמיניסטי וקו-נגיש, אז $latex A_{\mbox{min}}=A_{\mbox{det}}$. מכאן יותר קל להבין מה קרה בנוסחה $latex A_{\mbox{min}}=\left(\left(\left(A^{R}\right)_{\mbox{det}}\right)^{R}\right)_{\mbox{det}}$: החלק הפנימי, $latex \left(\left(A^{R}\right)_{\mbox{det}}\right)^{R}$, הוא פשוט מה שצריך לעשות כדי לקבל מ-$latex A$ שהתחלנו ממנו אוטומט שקול שהוא קו-דטרמיניסטי וקו-נגיש (שתי התכונות הללו מושגות בו זמנית על ידי ביצוע דטרמיניזציה). בדוגמת הצעצוע שנתתי, $latex A$ שלי לא היה קו-דטרמיניסטי, אבל מה שכן היה נכון הוא ש-$latex A^{R}$ קיבל את אותה שפה כמו $latex A$ (כי מילה היא מאורך אי זוגי אם ורק אם ההיפוך שלה כזה), ואותו $latex A^{R}$ דווקא כן מקיים את התכונה שהוא קו-דטרמיניסטי וקו-נגיש (כי $latex A$ היה דטרמיניסטי ונגיש). לכן כשביצענו את הדטרמיניזציה של $latex A^{R}$ קיבלנו אוטומט מינימלי עבור השפה של $latex A^{R}$, ובמקרה שלנו זו הייתה השפה שאנחנו מחפשים.

אז הקסם הוא בכך שדטרמיניזציה של אוטומט עשויה, בתנאים נחמדים מסויימים, לבנות ממנו את האוטומט המינימלי. זה לא באמת מופרך, אם חושבים על זה לרגע. דטרמיניזציה בונה אוטומט חדש, שמצביו הם קבוצות של מצבים של האוטומט המקורי – זה בדיוק גם מה שעשינו באלגוריתם הקודם שהצגנו. אבל הסיטואציה בכל זאת שונה – הקבוצות שנקבל לא יהיו מחלקות השקילות של היחס $latex \equiv$ (למשל, בדוגמה שלי, $latex q_{0}$ מתקבץ יחד עם $latex q_{2}$ למרות שאחד הוא מצב מקבל והשני איננו). יש בעיה מהותית לדבר בכלל על היחס $latex \equiv$ כי הוא הוגדר עבור אוטומטים דטרמיניסטיים, אבל $latex A$ שלנו עשוי להיות אי-דטרמיניסטי. לכן בואו נחזור לתיאור האוטומט המינימלי שנתתי בתחילת הפוסט – מצבי האוטומט הם השפות $latex u^{-1}L$. כלומר, אני אראה התאמה חח"ע ועל בין מצבי $latex A_{\mbox{det}}$ ובין השפות $latex u^{-1}L$. האינטואיציה ברורה – לכל $latex u\in\Sigma^{*}$, נעביר את המצב שאליו מגיעים על ידי קריאת $latex u$ ב-$latex A_{\mbox{det}}$ אל $latex u^{-1}L$ (דהיינו, אם $latex S=\hat{\delta}\left(q_{0},u\right)$, אז מבצעים $latex S\mapsto u^{-1}L$). כדי להיווכח בכך שההתאמה הזו היא בכלל פונקציה ושהיא חח"ע צריך להראות שלכל זוג מילים $latex u,v$ מתקיים ש-$latex \hat{\delta}\left(q_{0},u\right)=\hat{\delta}\left(q_{0},v\right)$ אם ורק אם $latex u^{-1}L=v^{-1}L$ – אנחנו מקבלים את אותו הפלט. מרגע שהראיתי את זה, סיימתי, כי ההתאמה היא בבירור על (הרי התחלנו עם $latex u\in\Sigma^{*}$ כלשהי, זה מבטיח שנוכל לכסות את כל ה-$latex u^{-1}L$-ים)

בכיוון אחד, אם $latex \hat{\delta}\left(q_{0},u\right)=\hat{\delta}\left(q_{0},v\right)$ אז מן הסתם לכל הרחבה של החישוב באמצעות $latex z$, אם יהיה חישוב מקבל באחד האוטומטים יהיה גם בשני. לכן $latex uz\in L\iff vz\in L$ מה שמראה ש-$latex u^{-1}L=v^{-1}L$. הכיוון המעניין הוא השני: אנו מניחים ש-$latex u^{-1}L=v^{-1}L$ וצריכים להראות שהמצבים שאליהם $latex A$ יכול להגיע על ידי קריאת $latex u$ הם בדיוק המצבים שאליהם $latex A$ יכול להגיע על ידי קריאת $latex v$. כאן מן הסתם ייכנסו לפעולה התכונות שמאפיינות את $latex A^{R}$.

בואו ניקח $latex p$ כך שקיימת ריצה של $latex A$ על $latex u$ שמסתיימת ב-$latex p$. האבחנה הראשונה שלנו היא שאפשר להמשיך את הריצה הזו ולהגיע למצב מקבל; זה נובע מכך ש-$latex A^{R}$ הוא אוטומט ישיג, ולכן $latex p$ ישיג ממצב התחלתי של $latex A^{R}$ – כלומר, ב-$latex A$ העסק מתהפך ואנחנו מקבלים שיש מצב מקבל של $latex A$ שישיג מ-$latex p$. כלומר, קיים $latex z$ כך ש-$latex uz\in L$, דהיינו $latex z\in u^{-1}L=v^{-1}L$, ולכן גם $latex vz\in L$. כלומר: קיימת ריצה של $latex A$ על $latex vz$ שמסתיימת במצב מקבל. עכשיו נכניס לתמונה את העובדה ש-$latex A^{R}$ הוא דטרמיניסטי; בפרט זה אומר שקיים לו מצב התחלתי יחיד ולכן ל-$latex A$ יש מצב מקבל יחיד, כלומר הריצה של $latex A$ על $latex vz$ מסתיימת באותו מצב כמו הריצה של $latex A$ על $latex uz$. בואו נסמן ב-$latex p^{\prime}$ את המצב שאליו הריצה הזו מגיעה אחרי סיום קריאת $latex v$.

מה למדנו? שב-$latex A$ קיימים שני מצבים, $latex p,p^{\prime}$, שעל ידי קריאת $latex z$ ניתן לעבור מכל אחד מהם אל המצב המקבל היחיד של $latex A$. זה אומר שב-$latex A^{R}$, על ידי קריאת $latex z^{R}$, אפשר להגיע גם ל-$latex p$ וגם ל-$latex p^{\prime}$. אבל הרי $latex A^{R}$ הוא דטרמיניסטי, ולכן זה אפשרי רק אם $latex p=p^{\prime}$. המסקנה: קיימת ריצה של $latex A$ על $latex v$ שמסתיימת ב-$latex p$, ולכן $latex \hat{\delta}\left(q_{0},u\right)\subseteq\hat{\delta}\left(q_{0},v\right)$. ההוכחה בכיוון השני זהה, וקיבלנו שהאיזומורפיזם שהגדרתי בין מצבי $latex A_{\mbox{det}}$ ובין השפות $latex u^{-1}L$ עובד. עדיין צריך להשתכנע ש-$latex A_{\mbox{det}}$ זהה לאוטומט שבונים מתוך $latex u^{-1}L$, אבל קל למדי לוודא את זה. סיימנו את הבניה הזו!

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

2 תגובות בנושא “משפט מייהיל-נרוד – נקודת מבט נוספת, ואלגוריתמי מינימיזציה”

  1. האם האלגוריתם הראשון (הופקרופט) יכול להיות אקספוננציאלי במספר המצבים?

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

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

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

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *