אוטומטים ושפות פורמליות/תכונות של שפות רגולריות/משפט מיהיל-נרוד: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 23:
== משפט מיהיל-נרוד ==
===מבוא ורעיון כללי===
הרעיון העומד מאחורי המשפט הוא לחלק את השפה L למחלקות שקילות
<math>x,y</math> מובילות לאותו המצב, האוטומט "שוכח" זאת, ומתנהג באופן זהה לכל סיפא שהי. במילים אחרות, האוטומט חייב להתנהג באופן זהה עבור המילה <math>xz</math> והמילה <math>yz</math> '''עבור כל סיפא <math>z</math> שהיא'''.
במקרה זה, נאמר ש-<math>x</math> ו-<math>y</math> שייכות לאותה מחלקת שקילות.
| |||