משפט מייהיל-נרוד

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

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

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

בואו נתחיל עם דוגמה פשוטה. השפה \( L=\left\{ w\in\left\{ a,b\right\} ^{*}\ |\ \left|w\right|\equiv_{2}0\right\} \) של כל המילים מאורך זוגי. אני רוצה לבנות אוטומט לשפה. ממה מתחילים? ובכן, ממה שחייבים. לאוטומט חייב להיות מצב התחלתי \( q_{0} \), אז אני מוסיף אותו לקבוצת המצבים של האוטומט. עכשיו אני שואל את עצמי - האם זה יהיה מצב מקבל או לא? התשובה לשאלה הזו נקבעת על פי השאלה האם \( \varepsilon \) שייכת לשפה או לא. אם היא כן - אז \( q_{0} \) חייב להיות מקבל אחרת אין שום סיכוי שנקבל את \( \varepsilon \); אם היא לא, אז אסור ל-\( q_{0} \) להיות מקבל. במקרה שלנו המסקנה היא ש-\( q_{0} \) יהיה מצב מקבל.

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

בואו נעצור שניה ונתאר בצורה קצת אחרת את מה שראינו כרגע. לפני דקה החלטתי ש-\( q_{0} \) יהיה מצב מקבל בגלל ש-\( \varepsilon\in L \) . רגע אחר כך החלטתי שאסור לי להגדיר \( \delta\left(q_{0},a\right)=q_{0} \) בגלל ש-\( a\notin L \). כלומר, מה שראיתי הוא שיש הפרדה בין \( \varepsilon \) ובין \( a \) - שתי המילים הללו שונות בצורה מהותית בכך שהאחת שייכת לשפה והשניה לא. המסקנה שלי הייתה שלא ייתכן שפונקציית המעברים \( \delta \) תעביר את שתיהן לאותו מקום - שחייב להתקיים \( \hat{\delta}\left(q_{0},\varepsilon\right)\ne\hat{\delta}\left(q_{0},a\right) \). זה אולי נשמע טריוויאלי בינתיים, אבל זה תופס את הרעיון הבסיסי שמאחורי מייהיל-נרוד.

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

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

בואו נבין מה המשמעות של הגדרת \( \delta\left(q_{1},a\right)=q_{0} \). זה אומר שיתקיים \( \hat{\delta}\left(q_{0},\varepsilon\right)=\hat{\delta}\left(q_{0},aa\right) \). כלומר, קיבלנו שתי מילים שהאוטומט מעביר לאותו מצב בדיוק. זה דורש שהן שתיהן יהיו בשפה ביחד, או ששתיהן לא יהיו בשפה ביחד, אחרת יש לנו בעיה ברורה. אבל קורה יותר מזה. אוטומט הוא הרי חסר זכרון. הוא לא יודע מה המילה שהביאה אותו למצב נתון. אם הוא הגיע לאותו מצב אחרי קריאת \( \varepsilon \) ואחרי קריאת \( aa \), אז המשך החישוב שלו יהיה זהה ולא משנה איזו מילה הביאה אותו למצב הזה.

זה אומר שלכל מילה \( z \) שאותה אנחנו קוראים החל מהרגע שבו הגענו למצב הזה, התשובה שהאוטומט יחזיר אחרי קריאת \( z \) הזו לא תהיה תלויה במה שהביא אותו אל המצב מלכתחילה. ולכן האוטומט צריך לענות את אותה תשובה על \( \varepsilon\cdot z \) ועל \( aa\cdot z \), וזאת לכל \( z \). האבחנה הזו היא לב העניין.

בואו נראה דוגמה אחרת. הפעם השפה תהיה \( L=\left\{ w\in\left\{ a,b\right\} ^{*}\ |\ \left|w\right|\not\equiv_{3}0\right\} \) - שפת כל המילים שאורכן אינו מתחלק ב-3. חיש קל ברור ש-\( \delta\left(q_{0},a\right)=q_{1} \) כך ש-\( q_{1} \) מקבל ו-\( q_{0} \) אינו מקבל (מדוע?), וכעת השאלה היא מה לעשות עם \( \delta\left(q_{1},a\right) \). מצד אחד, גם \( a \) וגם \( aa \) שניהם בשפה, ולכן ברמה העקרונית אם נגדיר \( \delta\left(q_{1},a\right)=q_{1} \) (ולכן \( \hat{\delta}\left(q_{0},aa\right)=\hat{\delta}\left(q_{0},a\right) \)) זה לא יגרום לשגיאה מיידית; אבל השגיאה חייבת להגיע בצעד הבא, כי \( aa\cdot a\notin L \) אבל \( a\cdot a\in L \) ולכן \( z=a \) היא מילה ש”מפרידה” בין \( a \) ובין \( aa \). המסקנה היא שאנחנו חייביים מצב מקבל חדש \( q_{2} \) כך ש-\( \delta\left(q_{1},a\right)=q_{2} \).

אם כן, מצאנו תכונה שמתארת האם זוג מילים הן כאלו שהאוטומט שבונים עבור השפה יכול להעביר לאותו מצב, או שאסור לו. אני אשתמש בסימון \( uR_{L}v \) כדי לתאר את הסיטואציה שבה \( u,v \) מקיימות את התכונה הזו; זה סימון מקובל לכך ששני איברים נמצאים יחד ביחס. תזכורת קצרה לגבי מהו יחס, פורמלית: פשוט אוסף של זוגות. אני כותב \( uR_{L}v \) במקום לכתוב \( \left(u,v\right)\in R_{L} \) פשוט כי זה יותר קומפקטי.

הנה ההגדרה הפורמלית, שבשלב הזה אני מקווה שכבר תהיה ברורה וכך גם המוטיבציה אליה: \( uR_{L}v \) אם ורק אם לכל \( z\in\Sigma^{*} \) מתקיים ש-\( uz\in L\iff vz\in L \).

עכשיו, היחס הזה מקיים שלוש תכונות נחמדות: ראשית, \( uR_{L}u \) לכל \( u\in\Sigma^{*} \) - זה די מובן מאליו למה. גם מובן מאליו למה אם \( uR_{L}v \) אז גם \( vR_{L}u \). התכונה השלישית יותר מעניינת: אם \( uR_{L}v \) וגם \( vR_{L}w \) אז \( uR_{L}w \). למה? פשוט, כי לכל \( z \) מתקיים ש-\( uz\in L\iff vz\in L\iff wz\in L \). שלוש התכונות הללו נקראות, בהתאמה, רפלקיסיבות, סימטריות וטרנזיטיביות, ויחס שמקיים את שלוש התכונות הללו נקרא יחס שקילות. המהות של יחס שקילות היא שהוא מעין הכללה של מושג השוויון - הוא אומר “שני האובייקטים הללו אמנם לא חייבים להיות זהים, אבל באספקט אחד שלהם שמעניין אותנו הם שווים”.

בהינתן איבר \( w \), אפשר להסתכל על קבוצת כל האיברים ששקולים לו על פי היחס, כלומר הקבוצה \( \left[w\right]_{R_{L}}\triangleq\left\{ u\in\Sigma^{*}\ |\ wR_{L}u\right\} \). לקבוצה כזו קוראים מחלקת השקילות של \( w \). זו תמיד קבוצה לא ריקה, כי \( w\in\left[w\right]_{R_{L}} \) (כי רפלקסיביות). יותר מזה, אם \( u\in\left[w\right]_{R_{L}} \) אז \( w\in\left[u\right]_{R_{L}} \) (כי סימטריות) ואם \( v\in\left[w\right]_{R_{L}}\cap\left[u\right]_{R_{L}} \) אז \( uR_{L}w \) (כי טרנזיטביות). המסקנה מכל אלו: אוסף מחלקות השקילות של כל המילים ב-\( \Sigma^{*} \), דהיינו \( \left\{ \left[w\right]_{R_{L}}\ |\ w\in\Sigma^{*}\right\} \) הוא חלוקה של \( \Sigma^{*} \) לתת-קבוצות שהן זרות זו לזו, לא ריקות, ואיחודן נותן את כל \( \Sigma^{*} \). את האוסף הזה נהוג לסמן \( \Sigma^{*}/R_{L}\triangleq\left\{ \left[w\right]_{R_{L}}\ |\ w\in\Sigma^{*}\right\} \). קוראים לאוסף הזה לפעמים “קבוצת המנה” של יחס השקילות. הגודל שלו הולך להיות חשוב מאוד בהמשך אז בואו ניתן לו סימון: \( \mbox{index}\left(R_{L}\right)=\left|\Sigma^{*}/R_{L}\right| \).

עכשיו אפשר לנסח את משפט מייהיל-נרוד פורמלית: שפה \( L \) היא רגולרית אם ורק אם \( \mbox{index}\left(R_{L}\right) \) סופי. יותר מכך: במקרה שבו \( L \) רגולרית, אז \( \mbox{index}\left(R_{L}\right) \) הוא מספר המצבים של אוטומט מינימלי עבור השפה \( L \). זה גם נותן אינטואיציה לגבי הסיבה שבגללה אין אוטומט לשפה לא רגולרית \( L \): מכיוון ש-\( \mbox{index}\left(R_{L}\right)=\infty \) לשפות כאלו, אז מספר המצבים באוטומט מינימלי עבורן היה אינסופי - וזה כמובן לא חוקי.

בואו נעבור להוכיח את המשפט. יש לנו שני כיוונים להוכיח. ראשית כל אני אראה שאם \( \mbox{index}\left(R_{L}\right) \) סופי אז קיים אוטומט סופי דטרמיניסטי שמקבל את \( L \), ואני אעשה את זה בצורה הכי ישירה שיש - אציג אוטומט עבור \( L \). ההוכחה הזו מקסימה מאוד, לטעמי, כי אנחנו הולכים לבנות את האוטומט הזה מתוך מחלקות השקילות של \( R_{L} \). לי זה קצת מזכיר את ההוכחה של משפט השלמות של גדל, אבל לא ארחיב על כך יותר מדי.

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

הדרך הכי טבעית לבנות אוטומט כזה היא לבנות את קבוצת המצבים כך שיש מצב לכל מילה, והקריאה של המילה מביאה את האוטומט אל המצב הזה. כלומר, נגדיר \( Q=\left\{ q_{w}\ |\ w\in\Sigma^{*}\right\} \). המצב ההתחלתי שלנו יהיה \( q_{\varepsilon} \), ואנחנו רוצים שיתקיים \( \hat{\delta}\left(q_{\varepsilon},w\right)=q_{w} \). די ברור שהדרך הנכונה להגדיר את פונקציית המעברים שלנו היא זו: \( \delta\left(q_{w},\sigma\right)=q_{w\sigma} \). כעת, מי יהיו המצבים המקבלים? בדיוק כאלו שמתאימים למילים שבשפה, כלומר \( F=\left\{ q_{w}\ |\ w\in L\right\} \). קחו רגע ותסבירו לעצמכם למה הבניה הזו באמת עובדת - הבעיה ה”קטנה” היחידה היא ש-\( Q \) היא אינסופית.

אז מה אומרים מייהיל-נרוד? פשוט מאוד - קחו את האוטומט הנאיבי הזה, ותנסו לצמצם אותו כך שנישאר רק עם מספר סופי של מצבים. המפתח לצמצום של אוטומט הוא יחס השקילות \( R_{L} \). מה הוא אומר? אם שתי מילים שקולות ב-\( R_{L} \), זה אומר שמרגע שהאוטומט סיים לקרוא אותן, המשך החישוב שלו יכול להיות זהה. כלומר, אין סיבה ששתי המילים הללו יובילו למצבים שונים; הן יכולות להוביל לאותו מצב בדיוק. לכן אם \( uR_{L}v \) אנחנו רוצים שהמצבים \( q_{u},q_{v} \) יהיו אותו מצב - לאחד אותם. אבל זה נכון לא רק לזוגות של מצבים - באופן כללי, לכל מחלקת שקילות של \( R_{L} \), כל המילים שבמחלקה יכולות להוביל לאותו מצב. לכן יהיה לנו מצב לכל מחלקת שקילות. שאר ההגדרות של האוטומט הן מה שקורה כשלוקחים את הבניה שלמעלה ומחליפים את המצבים במחלקות שקילות.

אם כן, אני מגדיר \( Q=\Sigma^{*}/R_{L}=\left\{ \left[w\right]_{R_{L}}\ |\ w\in\Sigma^{*}\right\} \). שימו לב לדמיון ל-\( \left\{ q_{w}\ |\ w\in\Sigma^{*}\right\} \) שלמעלה, רק שהחלפתי את \( q_{w} \) ב-\( \left[w\right]_{R_{L}} \). במקום מצב לכל מילה, אני לוקח מצב לכל מחלקת שקילות של מילים. בכתיב שלי אני כותב את אותה מחלקת שקילות הרבה פעמים (למשל, אם \( uR_{L}v \) אז \( \left[u\right]_{R_{L}}=\left[v\right]_{R_{L}} \) ולכן מחלקת השקילות הזו תופיע לפחות פעמיים) - אבל זכרו שכאשר כותבים קבוצה וחוזרים על אותו איבר כמה פעמים, הוא “נחשב” רק פעם אחת. אז אין לי חזרות מיותרות ואם מספר מחלקות השקילות סופי, מספר המצבים של האוטומט סופי. כמו קודם, מה שאנחנו רוצים שיתקיים הוא ש-\( \hat{\delta}\left(q_{0},w\right)=\left[w\right] \)

מה יהיה המצב ההתחלתי שלנו? כמובן, \( q_{0}=\left[\varepsilon\right] \) (בלי זה לא היה סיכוי שיתקיים השוויון על פונקציית המעברים לעיל).

ומה יהיו המצבים המקבלים? כמובן, \( F=\left\{ \left[w\right]\ |\ w\in L\right\} \).

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

בואו נסביר את זה יותר בפירוט. הפחד שלי הוא שקיימות מילים \( u,v \) כך ש-\( uR_{L}v \) ולכן \( \left[u\right]=\left[v\right] \), אבל משום מה לא יתקיים ש-\( u\sigma R_{L}v\sigma \). כלומר, נקבל \( \left[u\sigma\right]\ne\left[v\sigma\right] \). זה אומר שההגדרה \( \delta\left(\left[w\right],\sigma\right)=\left[w\sigma\right] \) היא תלויה בנציג שאני בוחר למחלקת השקילות: אם אני אבחר לייצג את המחלקה עם \( u \) אני אקבל פלט אחד, ואם אני אייצג אותה עם \( v \) אני אקבל פלט אחר. זה בלתי נסבל בהגדרה של פונקציה: הרעיון הבסיסי בפונקציה הוא שלכל קלט קיים פלט יחיד. לא ייתכן שלאותו קלט יהיו כמה פלטים שתלויים באופן שבו אנחנו מסמנים את הקלט. הוכחה כזו מראה שהפונקציה כפי שהגדרתי אותה היא מוגדרת היטב.

אז מה עושים? מוכיחים שזה לא יכול לקרות. נניח ש-\( \left[u\right]=\left[v\right] \) ונוכיח ש-\( \left[u\sigma\right]=\left[v\sigma\right] \) פשוט על פי הגדרה. לצורך כך צריך להיזכר בהגדרה של \( R_{L} \): צריך להראות שלכל \( z \) מתקיים \( u\sigma\cdot z\in L\iff v\sigma\cdot z\in L \). לצורך כך, נשתמש בנשק שלנו: ידוע ש-\( uR_{L}v \) ולכן לכל \( z^{\prime} \) מתקיים \( u\cdot z^{\prime}R_{L}v\cdot z^{\prime} \). אם כן, פשוט נבחר \( z^{\prime}=\sigma z \) וסיימנו.

בעצם הראינו כאן תכונה מעניינת נוספת של היחס \( R_{L} \) - תכונה שאקרא לה אינוריאנטיות מימין. הנה הגדרה כללית שלה: יחס \( R \) הוא אינוריאנטי מימין אם לכל \( u,v \) המקיימים \( uRv \) ולכל \( \sigma\in\Sigma \) מתיים ש-\( u\sigma Rv\sigma \) - גם אם אנחנו מאריכים לצד ימין את המילים \( u,v \) על ידי אותה אות אנחנו עדיין נשארים ביחס (ההפך לא נכון - ייתכנו שתי מילים לא שקולות שאחרי שמחברים להן עוד אות מימין הופכות לשקולות). התכונה הזו עוד תועיל לנו בהמשך.

בואו נוכיח שהבניה שלנו עובדת. ראשית כל, נוכיח באינדוקציה ש-\( \hat{\delta}\left(q_{0},w\right)=\left[w\right] \). זו הוכחה קלה כי הבניה מיועדת לכך שהיא תעבוד: עבור הבסיס \( w=\varepsilon \) זה נובע מייד מההגדרה - \( \hat{\delta}\left(q_{0},\varepsilon\right)=q_{0}=\left[\varepsilon\right] \); עבור צעד האינדוקציה, ניקח מילה מהצורה \( w\sigma \) כך שניתן להשתמש באינדוקציה על \( w \), וכעת \( \hat{\delta}\left(q_{0},w\sigma\right)=\delta\left(\hat{\delta}\left(q_{0},w\right),\sigma\right)=\delta\left(\left[w\right],\sigma\right)=\left[w\sigma\right] \) - שוב, נובע ישירות מהבניה.

עכשיו כמעט סיימנו, אבל יש נקודה טריקית אחת שעוד יהיה צורך להתייחס אליה. אנחנו רוצים להראות ש-\( w\in L\iff\hat{\delta}\left(q_{0},w\right)\in F \). לפי מה שראינו כבר, זה שקול להוכחה ש-\( w\in L\iff\left[w\right]\in F \). כיוון אחד הוא ברור: אם \( w\in L \) אז \( \left[w\right]\in F \) על פי בניית האוטומט. אבל הכיוון השני קצת פחות ברור - אם \( \left[w\right]\in F \) זה לא אומר מיידית ש-\( w\in L \): מה שזה אומר הוא שקיים \( u\in L \) כך ש-\( \left[w\right]=\left[u\right] \). אבל כל מה שצריך לעשות הוא להיזכר שוב בהגדרה \( R_{L} \): אם \( wR_{L}u \) אז לכל \( z \) מתקיים \( wz\in L\iff uz\in L \) ובפרט עבור \( z=\varepsilon \). מכיוון ש-\( u\in L \) נקבל ש-\( w\in L \) וסיימנו.

סיכום ביניים: הראינו שאם \( \mbox{index}\left(R_{L}\right) \) סופי אז \( L \) רגולרית. עכשיו אני רוצה להראות את הכיוון השני: שאם \( L \) רגולרית אז \( \mbox{index}\left(R_{L}\right) \) סופי. ואני הולך לעשות את זה על ידי כך שאוכיח ש-\( \mbox{index}\left(R_{L}\right) \) הוא מספר המצבים באוטומט מינימלי עבור \( L \) - מן הסתם זה גם מוכיח מייד שהמספר הזה סופי (כי \( L \) רגולרית אז קיים לה אוטומט עם מספר מצבים סופי).

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

פורמלית נגדיר \( uR_{A}v \) אם ורק אם \( \hat{\delta}\left(q_{0},u\right)=\hat{\delta}\left(q_{0},v\right) \) באוטומט \( A \). קל מאוד להוכיח שזה יחס שקילות. עוד דבר שקל מאוד לראות הוא ש-\( \mbox{index}\left(R_{A}\right)\le\left|Q\right| \). מדוע? כי אפשר להגדיר התאמה חח”ע מקבוצת מחלקות השקילות של \( R_{A} \) אל קבוצת המצבים של \( A \): לכל \( \left[w\right] \) נתאים את המצב \( \hat{\delta}\left(q_{0},w\right) \). קל לראות שההתאמה הזו מוגדרת היטב והיא חח”ע. ולמה ייתכן שאין שוויון, כלומר ש-\( \mbox{index}\left(R_{A}\right)<\left|Q\right| \)? כי ב-\( A \) עשויים להיות מצבים “מיותרים” שאי אפשר להגיע אליהם על ידי קריאת אף מילה.

כל מה שנשאר לי להראות, אם כן, הוא ש-\( \mbox{index}\left(R_{L}\right)\le\mbox{index}\left(R_{A}\right) \) לכל \( A \) המקיים \( L\left(A\right)=L \). אני אוכיח משהו קצת יותר חזק מכך - שכל מחלקת שקילות של \( R_{L} \) היא איחוד של מחלקת שקילות אחת או יותר של \( R_{A} \). כלומר, אם \( R_{L} \) מחלק לנו את \( \Sigma^{*} \) לתת-קבוצות, הרי ש-\( R_{A} \) לוקח את תת הקבוצות הללו ולכל היותר מחלק אותן עוד קצת (במקום לבצע חלוקה שונה לגמרי שמניבה חתיכות שאי אפשר לחבר כדי לקבל את החתיכות של \( R_{L} \)). פורמלית, מה שאני רוצה להראות הוא שלכל \( u\in\Sigma^{*} \) מתקיים ש-\( \left[u\right]_{R_{A}}\subseteq\left[u\right]_{R_{L}} \) (ולכן \( \left[u\right]_{R_{L}}=\bigcup_{w\in\left[u\right]_{R_{L}}}\left[w\right]_{R_{A}} \) - נסו להוכיח זאת!). על סיטואציה כזו אומרים ש-\( R_{A} \) “מעדן” את \( R_{L} \) - כי החלוקה ש-\( R_{A} \) מגדיר היא כמו זו של \( R_{L} \) רק יותר “עדינה”.

אם כן, בואו ניקח \( v\in\left[u\right]_{R_{A}} \) ונוכיח ש-\( v\in\left[u\right]_{R_{L}} \). כלומר, אנחנו יודעים ש-\( uR_{A}v \) ורוצים להוכיח ש-\( uR_{L}v \). אם כן, ניקח \( z\in\Sigma^{*} \) כלשהי ונוכיח ש-\( uz\in L\iff vz\in L \). אבל, אם אתם עדיין נושמים בכלל, זה ממש קל! מכיוון ש-\( uR_{A}v \) אנחנו יודעים ש-\( \hat{\delta}\left(q_{0},u\right)=\hat{\delta}\left(q_{0},v\right) \) ועל כן \( \hat{\delta}\left(q_{0},uz\right)=\hat{\delta}\left(q_{0},vz\right) \) ומכאן התוצאה נובעת מאליה.

סיימנו, אבל אפשר להכליל את התוצאה הזו עוד קצת. בואו ננסה להבין באילו תכונות של \( A \) ושל \( R_{A} \) השתמשנו בהוכחה. ראשית, השתמשנו בכך שאם \( uR_{A}v \) אז \( uzR_{A}vz \) - זו מעין הכללה של מה שקראתי לו “אינוריאנטיות מימין” כי כאן אנחנו משרשרים מצד ימין מילה ולא אות בודדת, אבל די ברור ששתי ההגדרות הללו שקולות (כי אפשר לשרשר את כל \( z \) “אות-אות”. כלומר, השתמשנו בכך ש-\( R_{A} \) הוא יחס אינוריאנטי מימין. בתכונה השניה של \( R_{A} \) השתמשתי בצורה קצת יותר מובלעת - אמרתי שאם \( uR_{A}v \) אז \( u\in L\iff v\in L \) (איפה?) מכיוון שאפשר לחשוב על \( L \) בתור מגדירה יחס שקילות משל עצמה (שכולל בדיוק שתי מחלקות - \( L \) והמשלימה של \( L \)) נוח לקרוא לתכונה הזו “\( R_{A} \) מעדן את \( L \)”.

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

ההוכחה של התוצאה הזו זהה להוכחה שכבר ראינו. אם \( R \) הוא יחס שקילות אינוריאנטי מימין שמעדן את \( L \) אז ניקח \( uRv \) ונוכיח ש-\( uR_{L}v \): ניקח \( z \), אז \( uzRvz \) בגלל האינוריאנטיות מימין, ולכן \( uz\in L\iff vz\in L \), בגלל ש-\( R \) מעדן את \( L \). למרות שזו הוכחה מגוחכת של שורה אחת אני חושב שהיא מצויינת, כי היא מאפשרת לנו “להרגיש” מה בעצם כל כך מיוחד ביחס \( R_{L} \) ולמה הוא הדבר שהכי טבעי לדבר עליו בהקשר הזה.

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

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

בואו נראה איך את \( L=\left\{ a^{n}b^{n}\ |\ n\in\mathbb{N}\right\} \) המשפט אוכל בלי מלח. פשוט נסתכל על קבוצת המילים \( \left\{ a^{n}\ |\ n\in\mathbb{N}\right\} \). זו קבוצה אינסופית. קל לראות שאין בה זוג מילים שקולות: ניקח \( a^{n},a^{k} \) כך ש-\( n\ne k \), ואז קל להציג \( z \) שמפריד ביניהן: \( z=b^{n} \), כי \( a^{n}b^{n}\in L \) אבל \( a^{k}b^{n}\notin L \). זהו.

גם את \( L=\left\{ ww\ |\ w\in\left\{ a,b\right\} ^{*}\right\} \) המשפט אוכל בקלות. נבחר את קבוצת המילים \( \left\{ a^{n}b\ |\ n\in\mathbb{N}\right\} \) ועבור \( a^{n}b,a^{k}b \) מילה מפרידה תהיה \( z=a^{n}b \), כי בבירור \( a^{k}ba^{n}b \) היא לא מהצורה \( ww \) (כי אם היא כן, אז \( w \) מסתיימת ב-\( b \) כי \( ww \) מסתיימת ב-\( b \), אבל זה גורר ש-\( w=a^{n}b \) וגם \( w=a^{k}b \)).

נעבור עכשיו לדוגמת הראשוניים, \( L=\left\{ a^{p}\ |\ p\mbox{ is prime}\right\} \). מה יוכיח במקרה הזה שהשפה לא רגולרית? קבוצה אינסופית \( A \) של מספרים טבעיים כך שלכל \( a,b\in A \) שונים זה מזה, קיים \( d \) טבעי כך שבדיוק אחד מבין \( a+d,b+d \) הוא מספר ראשוני.

למצוא קבוצה כזו - זה קל. אפילו כל הטבעיים מקיימים את התכונה הזו. אבל להוכיח את זה - זה כבר פחות טריוויאלי. הנה הוכחה אפשרית אחת. ראשית, נניח בלי הגבלת הכלליות ש-\( a<b \). כעת נמצא ראשוני \( p>b \) כך שכל \( b-1 \) המספרים שבאים אחרי \( p \) הם בודאות לא ראשוניים. אם מצאנו כזה, סיימנו, כי אז נסמן \( d=p-a \) ונקבל ש-\( a+d \) ראשוני אבל \( b+d=p+\left(b-a\right)\le p+\left(b-1\right) \) לא ראשוני. למה קיים \( p \) כזה? ובכן, בואו ונסתכל על הקבוצה \( \left\{ b!+2,b!+3,\dots,b!+b\right\} \). המספר הראשון בקבוצה מתחלק ב-2, השני ב-3 וכן הלאה, ויש בקבוצה בסך הכל \( b-1 \) איברים. ניקח את \( p \) להיות הראשוני הגדול ביותר שקטן מ-\( b!+2 \) וסיימנו.

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