אוטומטים ושפות פורמליות/תכונות של שפות רגולריות/משפט מיהיל-נרוד

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

רקע

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

יחס שקילות

יחס בינארי R מעל קבוצה A הוא תת-קבוצה של המכפלה הקרטזית $A\times A$. בסימנים: $\ {\mathcal {R}}\subseteq A\times A$. כלומר: הוא קבוצה של זוגות סדורים כך שכל איבר בזוג שייך ל-A. אם $\ (a,b)\in {\mathcal {R}}$ אזי מקובל לסמן $\ a{\mathcal {R}}b$.

יחס R מעל קבוצה A נקרא יחס שקילות אם הוא מקיים את התכונות הבאות:

1. רפלקסיביות: כל איבר עומד ביחס, כלומר $\ a{\mathcal {R}}a$ לכל $\ a\in A$. למשל, תכונה זו מתקיימת תמיד עבור היחס "שווה ל", כי כל איבר תמיד שווה לעצמו.
2. סימטריות: אם a עומד ביחס עם b אזי גם b עומד ביחס עם a, כלומר $\ a{\mathcal {R}}b\Leftrightarrow b{\mathcal {R}}a$. לדוגמה: יחס האחווה "אח של" הוא סימטרי כי אם a אח של b אז גם b אח של a. לעומת זאת, יחס ההורות "a אב של b" איננו סימטרי.
3. טרנזיטיביות: אם a נמצא ביחס ל-b ו-b נמצא באותו היחס ל-c אזי גם בין a ל-c מתקיים אותו היחס, ובניסוח פורמלי: $\ a{\mathcal {R}}b,b{\mathcal {R}}c\Rightarrow a{\mathcal {R}}c$. למשל, אם לסוס a צבע זהה לזה של סוס b, ול- b צבע זהה לשל c, אז ל- a אותו צבע כמו ל- c.

מחלקות שקילות

דוגמא למחלקות שקילות של עיגול. כל מחלקת שקילות מסומנת בצבע אחד. שתי נקודות בעלות אותו הצבע נמצאות באותה מחלקת שקילות.

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

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

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

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

מבוא ורעיון כללי

הרעיון העומד מאחורי המשפט הוא לחלק את כל המלים ($\ \Sigma ^{*}$) למחלקות שקילות המתאימות למצבי אוטומט סופי. נניח שעבור אוטומט סופי מסויים, עיבוד המילה $x$ מוביל את האוטומט למצב $q_{1}$, ונניח כי גם המילה $y$ מובילה את האוטומט למצב $q_{1}$. באופן דומה ללמת הניפוח, ה"זיכרון" היחידי של האוטומט הוא המצב, ולכן אם שתי המילים $x,y$ מובילות לאותו המצב, האוטומט "שוכח" זאת, ומתנהג באופן זהה לכל סיפא שהיא. במילים אחרות, האוטומט חייב להתנהג באופן זהה עבור המילה $xz$ והמילה $yz$ עבור כל סיפא $z$ שהיא. במקרה זה, נאמר ש-$x$ ו-$y$ שייכות לאותה מחלקת שקילות.

הגדרה

לכל שפה $L$ נגדיר את היחס $\ R_{L}$ המוגדר מעל $\ \Sigma ^{*}$ באופן הבא:
$(x,y)\in R_{L}$ אם"ם לכל מילה $z$ מתקיים אחד מהבאים:

1. המילים $xz$ ו-$yz$ שייכות שתיהן ל-$L$, או
2. המילים $xz$ ו-$yz$ שתיהן אינן שייכות ל-$L$.

אם קיימת מילה $z$ כך שאחת מהמילים בשפה והשניה אינה בשפה, נכנה את $z$ מילה מפרידה, ונובע ש-$x$ ו-$y$ אינן באותה מחלקת שקילות, $(x,y)\notin R_{L}$.

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

מספר המצבים באוטומט (סופי דטרמיניסטי) המינימלי אשר מקבל את L הוא כמספר מחלקות השקילות של $\ R_{L}$.

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

הוכחת המשפט

עבור שפה L נבנה א"ד המקבל אותה, כאשר המצבים של האוטומט יהיו מחלקות השקילות השונות. נסמן ב$[x]$ את מחלקת השקילות המכילה את המילה $x$ (ייתכנו סימונים נוספים לאותה מחלקה, למשל, אם המילה y באותה מחלקת שקילות, אזי $[y]$ מתייחס לאותה מחלקת שקילות).

האוטומט מוגדר באופן הבא:

• מצבי האוטומט הינם מחלקות השקילות השונות של L.
• המצב ההתחלתי הינו $[\epsilon ]$.
• פונקציית המעברים מוגדרת על ידי $\delta ([x],a)=[xa]$, לכל אות $a\in \Sigma$ ולכל מחלקת שקילות $[x]\in Q$.
  חשוב לציין כי פונקציה זו מוגדרת היטב: לא ייתכן ששתי מילים $x,y$ נמצאות באותה מחלקת שקילות, ואילו אם נשרשר אות נוספת $z$ נקבל שתי מחלקות שקילות שונות $[xz]\neq [yz]$, מכיוון שאם כך, הרי $z$ הינה מילה מפרידה, בסתירה לכך ש-$x,y$ שייכות לאותה מחלקת שקילות.
• מצב מקבל הוא כל מצב $[x]$ עבור מילה בשפה, $x\in L$.

נוכיח שהאוטומט לעיל מקבל את השפה $L$. עובדה זו נובעת מטענת העזר הבאה:

טענה: טענת עזר

לאחר עיבוד המילה $w$, האוטומט נמצא במצב $[w]$.

הוכחה: נוכיח באינדוקציה על אורך המילה $n$.

1. בסיס: $n=0$, המכונה מתחילה במצב $[\epsilon ]$ על פי הגדרתה, ולכן הטענה מתקיימת.
2. צעד: נניח כי טענת העזר מתקיימת עבור מילים באורך $n=k$, ונראה כי מתקיימת למילים באורך $n=k+1$. תהי המילה $w=w_{1}w_{2}\ldots w_{k}w_{k+1}$ קלט האוטומט. לפי הנחת האינדוקציה, לאחר עיבוד $w_{1}\ldots w_{k}$ המכונה נמצאת במצב $[w_{1}\ldots w_{k}]$, כעת מתבצע המעבר $\delta ([w_{1}\ldots w_{k}],w_{k+1})$ שעל-פי הגדרת האוטומט מוביל את המכונה למצב $[w]$ כנדרש.

מכיוון שכל מילה $x\in L$ הניתנת כקלט לאוטומט מובילה אותו למצב $[x]$ ומצב זה הינו מצב מקבל לפי ההגדרה, הרי שהמכונה מקבלת את כל המילים ב-$L$, כלומר הראינו כי $L\subseteq L(M)$.

הכיוון השני קל להוכחה: אם מילה מסויימת $x$ מתקבלת על-ידי האוטומט, אזי המצב $[x]$ הוא מצב מקבל. נניח בשלילה ש$x\notin L$, אזי קיימת מילה $y\in L$ כך ש$[y]=[x]$ (אחרת לא ייתכן ש$[x]$ הוא מצב מקבל, בהתאם להגדרת המצבים המקבלים). אבל, זו סתירה, מכיוון שהמילה $z=\epsilon$ הינה מילה מפרידה בין $x,y$, כי $yz\in L$ ואילו $xz\notin L$. מכאן נובע כי $L(M)\subseteq L$.

לסיום, נראה שהמכונה הנ"ל הינה מינימלית, כלומר בעלת מספר המצבים הקטן ביותר האפשרי. לשם כך נעשה שימוש ביחס שקילות נוסף (בדומה למה שהוסבר בפסקה "הרעיון הכללי"). בהינתן אוטומט כלשהו $\ A$, היחס $\ R_{A}$ המוגדר מעל $\ \Sigma ^{*}$ מוגדר כך ששתי מילים נמצאות באותה מחלקת שקילות אם קריאתן מביאה את האוטומט לאותו המצב. מספר מצבי האוטומט $\ A$ הוא לפחות כמספר מחלקות השקילות של היחס $\ R_{A}$, כי לכל מצב שניתן להגיע אליו באוטומט ניתן להתאים מחלקת שקילות שנציגתה היא מילה שמביאה את האוטומט למצב זה.

אם $\ L$ היא שפה רגולרית ו-$\ A$ אוטומט כלשהו עבורה, ניתן להראות כי היחס $\ R_{A}$ מעדן את היחס $R_{L}$, כלומר $\ R_{A}\subseteq R_{L}$. מכך נובע שמספר מחלקות השקילות של $\ R_{L}$ קטן ממספר מחלקות השקילות של $\ R_{A}$ - בפרט, הוא סופי, ומספר מצבי האוטומט שמושרה על ידי $\ R_{L}$ קטן או שווה למספר מצבי האוטומט $A$. [כדי למנוע בלבול, נדגיש כי ככל שהיחס מכיל יותר אלמנטים, יש בו פחות מחלקות שקילות. למשל, אם היחס הוא מקסימלי $R=A\times A$, אזי יש בו רק מחלקת שקילות אחת! כלל שמספר מחלקות השקילות גדל, יש יותר אברים שנמצאים בשתי מחלקות שונות, ולכן היחס $R$ יהיה תת-קבוצה קטנה יותר].

האבחנה לפיה $\ R_{A}\subseteq R_{L}$ נובעת מכך שאם $\ xR_{A}y$ אז לאחר קריאת שתי המילים יגיע האוטומט $\ A$ לאותו מצב, ועל כן לכל סיפא $\ z$ שקורא האוטומט לאחר מכן הוא יגיע גם כן לאותו מצב. כלומר, האוטומט יחזיר תשובה זהה על $\ xz$ ועל $\ yz$ לכל $\ z$, ולכן $xR_{L}y$, לפי הגדרה.

הפרק הקודם: למת הניפוח לשפות רגולריות

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

הפרק הבא: ביטויים רגולריים