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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Buy Me a Coffee at ko-fi.com