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

משפט מייהיל-נרוד הוא תוצאה בתורת השפות הפורמליות. המשפט נותן אפיון של שפות רגולריות ומסביר את מבנה האוטומט המינימלי שמקבל אותן. הוא נקרא על שמם של אניל נרוד וג'ון מייהיל (1958).

נגדיר יחס שקילות R_L על כל המילים מעל אלפבית נתון. עבור שתי מילים x ו-y נאמר x R_L y אם ולכל מילה z ההשלמה xz שייכת לשפה L בדיוק כשההשלמה yz שייכת ל-L. מילה z שאינה מקיימת תנאי זה נקראת מילה מפרידה או זנב מפריד בין x ו-y.

המשפט קובע: מספר המצבים באוטומט סופי דטרמיניסטי (מכונה עם מספר סופי של מצבים וטרנזicije ברורות) המינימלי שמקבל את L שווה למספר מחלקות השקילות של R_L. אם קיימות אינסוף מחלקות שקילות, לא קיים אוטומט סופי הדטרמיניסטי שמקבל את L, ולכן השפה אינה רגולרית.

בנוסף המשפט מתאר בנייה קונסטרוקטיבית של האוטומט המינימלי כאשר מספר מחלקות השקילות סופי. מצבי האוטומט הם המחלקות [x]. המצב ההתחלתי הוא מחלקת המילה הריקה [ε]. המצבים המקבלים הם המחלקות שמכילות מילים שב-L. פונקציית המעבר מוגדרת על ידי δ([x],a) = [xa]. קל להראות שהגדרה זו תקפה.

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

השפה L = {a^n b^n | n ∈ N} אינה רגולרית. לפי מייהיל-נרוד יש לה אינסוף מחלקות שקילות. מספיק להציג קבוצה אינסופית של מילים שאין שתי מילים בהן באותה מחלקת שקילות. למשל הקבוצה {a, a^2, a^3, ...}. לכל m ≠ n המילים a^n ו-a^m מופרדות על ידי z = b^n: a^n b^n שייכת ל-L בעוד ש-a^m b^n לא שייכת.

אם יש רק סופי מחלקות שקילות, אפשר לבנות אוטומט שמצביו הם המחלקות הללו. בקריאת מילה w האוטומט מגיע למחלקה [w], וזה מוודא שהאוטומט מקבל בדיוק את L. מינימיות מספר המצבים נובעת מהשוואה ליחס שקילות אחר R_A שמתקבל מאוטומט כלשהו A: x R_A y אם קריאת x ו-y מובילה לאותו מצב ב-A. עבור כל אוטומט A שמקבל את L היחס R_A עדין את R_L, כלומר R_A ⊆ R_L. לכן מספר מחלקות R_L לא גדול ממספר מצבי כל אוטומט מקבל, ומכאן נובעת מינימיות המימוש שהוצג.

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

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

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

השפה של כל המילים שאורכן זוגי מתחלקת לשתי קבוצות: זוגיות ואי-זוגיות. זו הסיבה שמכונה מינימלית לשפה זו צריכה רק שני מצבים. המצב ההתחלתי הוא גם מקבל.

השפה L = {a^n b^n} לא רגולרית. ניתן להראות שיש לה אינסוף קבוצות. ניקח את המילים a, a^2, a^3, ... . לכל שני מספרים שונים m ו-n, המילה b^n תפריד בין a^n ל-a^m. כך אין חיבור קבוצות סופי.

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