הצגת המקור של הדף "משפט מייהיל-נרוד"

בתורת [[שפה פורמלית|השפות הפורמליות]], '''משפט מייהיל-נרוד''' הוא [[משפט (מתמטיקה)|משפט]] אשר מספק אפיון של משפחת [[שפה רגולרית|השפות הרגולריות]] ומסייע להבנת המבנה של [[אוטומט סופי דטרמיניסטי|האוטומט]] המינימלי אשר מקבל אותן. המשפט נקרא על שם [[אניל נרוד]] ו[[ג'ון מייהיל]] אשר הוכיחו אותו בשנת [[1958]].

==ניסוח פורמלי==
המשפט מתבסס על [[יחס שקילות]] המוגדר בצורה הבאה: בהינתן [[שפה פורמלית|שפה]] <math>L</math> מעל אלפבית <math>\Sigma</math>, היחס <math>R_L</math> מוגדר מעל <math>\Sigma^*</math> בצורה הבאה: <math>xR_L y</math> [[אם ורק אם]] לכל <math>z \in\Sigma^*</math> המילים  <math>xz, yz</math> שייכות שתיהן לשפה <math>L</math> או ששתיהן אינן שייכות לשפה <math>L</math>. כלומר:

<math>x R_L y \Leftrightarrow \forall z \in \Sigma^* (xz \in L \Leftrightarrow yz \in L)</math>.

מילה <math>z \in \Sigma^*</math> שאינה מקיימת תנאי זה נקראת מילה מפרידה או זנב מפריד בין  <math>x,y</math>.

משפט מייהיל-נרוד אומר כי מספר המצבים המינימלי באוטומט סופי דטרמיניסטי אשר מקבל את <math>L</math> הוא כמספר [[מחלקת שקילות|מחלקות השקילות]] של <math>R_L</math>. בפרט, אם קיימות אינסוף [[מחלקות שקילות]] לא קיים אוטומט שכזה, ולכן השפה אינה רגולרית. המשפט גם מתאר את מבנה האוטומט המינימלי המקבל את השפה במקרה שמספר מחלקות השקילות הוא סופי, ומספק דרך קונסטרוקטיבית לבנות אוטומט כזה במקרה שמחלקות השקילות ידועות לנו: מצבי האוטומט יהיו מחלקות השקילות (כשהמצב ההתחלתי הוא <math>\left[\epsilon\right]</math>), המצבים המקבלים יהיו מחלקות שמיוצגות בידי מילים השייכות לשפה <math>L</math> ופונקציית המעברים של האוטומט תוגדר על ידי <math>\delta(\left[x\right],a)=\left[xa\right]</math> (קל להראות כי [[פונקציה]] זו [[מוגדר היטב|מוגדרת היטב]]).

==דוגמאות==
===שפה רגולרית===
עבור שפת כל המילים שאורכן [[מספר זוגי|זוגי]] (כולל אורך אפס), קיימות עבור היחס <math>R_L</math> בדיוק שתי [[מחלקת שקילות|מחלקות שקילות]] - מחלקה אחת היא קבוצת כל המילים מאורך זוגי, והמחלקה השנייה היא קבוצת כל המילים מאורך אי זוגי. כדי לראות זאת די לשים לב כי אם הזוגיות של אורך המילים <math>x,y</math> זהה, היא נותרת כזו גם כאשר מוסיפים לשתיהן סיפא <math>z</math> כלשהי. לכן, עבור כל שתי מילים בעלות זוגיות זהה מתקיים היחס <math>R_L</math>. (ועבור מילים בעלות זוגיות שונה, לא מתקיים היחס).

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

===שפה שאינה רגולרית===
ישנן מספר הוכחות לכך שהשפה <math>L=\left\{a^nb^n|n\isin\mathbb{N}\right\}</math> אינה רגולרית. הוכחה המתבססת על משפט נרוד מראה כי עבור היחס <math>R_L</math> קיימות [[אינסוף]] מחלקות שקילות. לשם כך אין צורך למצוא את כל מחלקות השקילות או לכתוב אותן במפורש, אלא די להציג [[קבוצה אינסופית]] של מילים כך שאין שתי מילים מתוכה הנמצאות באותה מחלקת שקילות.

בהקשר של השפה הנוכחית, קבוצה כזו היא למשל <math>\left\{a,a^2,a^3,\dots,\right\}</math>. כדי לראות זאת די להראות כי עבור <math>m,n</math> שרירותיים השונים זה מזה, <math>a^n</math> ו-<math>a^m</math> אינם שייכים לאותה מחלקת שקילות - כלומר, קיימת מילה <math>z</math> שמפרידה בינן. דוגמה למילה <math>z</math> שכזו היא <math>z=b^n</math>, שכן <math>a^nz=a^nb^n \in L</math> ואילו <math>a^mz=a^mb^n \notin L</math>.

==רעיון ההוכחה==
אם מספר מחלקות השקילות של <math>R_L</math> הוא סופי, האוטומט שהוצג לעיל שמצביו הם מחלקות השקילות של <math>R_L</math> מקבל את <math>L</math>. כדי לראות זאת די להוכיח ב[[אינדוקציה]] כי לאחר קריאת המילה <math>w</math> האוטומט יגיע למצב <math>[w]</math>. מכיוון שהמצבים המקבלים הוגדרו בתור המחלקות שמיוצגות על ידי המילים ששייכות לשפה, ומכיוון שאם במחלקה יש מילה השייכת לשפה כל המילים בה שייכות לשפה, הדבר מבטיח את נכונות האוטומט.

מינימליות מספר המצבים של האוטומט הזה מתבססת על שימוש ביחס שקילות נוסף. בהינתן אוטומט כלשהו <math>A</math>, היחס <math>R_A</math> מתקיים עבור כל שתי מילים שקריאתן מביאה את האוטומט לאותו המצב. כלומר:

<math>x R_A y \Leftrightarrow \hat{\delta}(q_0,x) = \hat{\delta}(q_0,y)</math>.

מספר מצבי האוטומט <math>A</math> הוא לפחות כמספר מחלקות השקילות של היחס <math>R_A</math>, כי לכל מצב שניתן להגיע אליו באוטומט ניתן להתאים מחלקת שקילות שנציגתה היא מילה שמביאה את האוטומט למצב זה.

אם <math>L</math> היא שפה רגולרית ו-<math>A</math> אוטומט כלשהו שמקבל אותה, ניתן להראות כי היחס <math>R_A</math> [[חלוקה (תורת הקבוצות)#יחס העידון|מעדן]] את היחס <math>R_L</math>, כלומר <math>R_A\subseteq R_L</math>. מכך נובע שמספר מחלקות השקילות של <math>R_L</math> קטן ממספר מחלקות השקילות של <math>R_A</math>. בפרט, הוא סופי, ומספר מצבי האוטומט שמושרה על ידי <math>R_L</math> קטן או שווה למספר מצבי האוטומט <math>A</math>.

האבחנה לפיה <math>R_A \subseteq R_L</math> נובעת מכך שאם <math>x R_A y</math> אז לאחר קריאת שתי המילים יגיע האוטומט <math>A</math> לאותו מצב, ועל כן לכל סיפא <math>z</math> שקורא האוטומט לאחר מכן הוא יגיע גם כן לאותו מצב. כלומר, האוטומט יחזיר תשובה זהה על <math>xz</math> ועל <math>yz</math> לכל <math>z</math>, ועל כן <math>x R_L y</math>.

== לקריאה נוספת ==
* {{פא"ר|מספר=418|שם הספר=אוטומטים ושפות פורמליות א|כותב=שמואל זקס ו[[נסים פרנסיז]]|שנה=2000}}, עמ' 249-287

==קישורים חיצוניים==
{{מיזמים|ויקיספר=אוטומטים ושפות פורמליות}}
* {{לא מדויק|2015/02/11/myhill_nerode_theorem|משפט מייהיל-נרוד}}
*{{וידאו}}גדי אלכסנדרוביץ, [https://www.youtube.com/watch?v=d9DLf3KujsM&list=PLW3u28VuDAHIg10rx2c45wo-F03fDfT-v&index=13 משפט נרוד], מתוך הרצאה בקורס "אוטומטים ושפות פורמליות", טכניון, 2018

[[קטגוריה:שפות פורמליות]]
[[קטגוריה:אוטומטים]]
[[קטגוריה:משפטים במדעי המחשב|מייהיל-נרוד]]