אוטומטים ושפות פורמליות/תכונות של שפות רגולריות/משפט מיהיל-נרוד: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
←‏רקע: מחלקות שקילות - מויקי
Gran (שיחה | תרומות)
המשפט
שורה 19:
 
לדוגמה: בהנחה שכל אדם בעולם הוא תושב של מדינה אחת ויחידה, הרי היחס "בעל תושבות משותפת" מחלק את כל תושבי העולם למחלקות שקילות, שכל אחת מהן מכילה את כל תושביה של מדינה מסוימת.
 
 
== משפט מיהיל-נרוד ==
===מבוא ורעיון כללי===
הרעיון העומד מאחורי המשפט הוא לחלק את השפה L למחלקות שקילות המתאימים למצבי אוטומט סופי. נניח שעבור אוטומט סופי מסויים, עיבוד המילה <math>x</math> מוביל את האוטומט למצב <math>q_1</math>, ונניח כי גם המילה <math>y</math> מובילה את האוטומט למצב <math>q_1</math>. באופן דומה ללמת הניפוח, ה"זיכרון" היחידי של האוטומט הוא המצב, ולכן אם שתי המילים
<math>x,y</math> מובילות לאותו המצב, האוטומט "שוכח" זאת, ומתנהג באופן זהה לכל סיפא שהי. במילים אחרות, האוטומט חייב להתנהג באופן זהה עבור המילה <math>xz</math> והמילה <math>yz</math> '''עבור כל סיפא <math>z</math> שהיא'''.
במקרה זה, נאמר ש-<math>x</math> ו-<math>y</math> שייכות לאותה מחלקת שקילות.
 
===הגדרה===
לכל שפה <math>L</math> נגדיר את יחס השקילות <math>R_L</math> באופן הבא:{{ש}}
<math> (x,y)\in R_L</math> אם"ם לכל מילה <math>z</math> מתקיים אחד מהבאים:
# המילים <math>xz</math> ו-<math>yz</math> שייכות שתיהן ל-<math>L</math>, או
# המילים <math>xz</math> ו-<math>yz</math> שתיהן אינן שייכות ל-<math>L</math>.
אם קיימת מילה <math>z</math> כך שאחת מהמילים בשפה והשניה אינה בשפה, נכנה את <math>z</math> '''מילה מפרידה''', ונובע ש-<math>x</math> ו-<math>y</math> אינן באותה מחלקת שקילות, <math> (x,y)\notin R_L</math>.
{{משפט|שם=משפט מיהיל-נרוד|
תוכן=מספר המצבים המינימלי באוטומט סופי דטרמיניסטי אשר מקבל את L הוא כמספר מחלקות השקילות של <math>\ R_L</math>}}
כתוצאה ממשפט זה, אם קיימות אינסוף מחלקות שקילות, אזי לא קיים אוטומט סופי המקבל את L, כלומר, במקרה זה L היא שפה לא-רגולרית.