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

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