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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
←‏הוכחת המשפט: הוכחת הכיוון השני
Gran (שיחה | תרומות)
←‏הוכחת המשפט: מינמליות, מבוסס על ויקיפדיה.
שורה 55:
מכיוון שכל מילה <math>x\in L</math> הניתן כקלט לאוטמט מובילה אותו למצב <math>[x]</math> ומצב זה הינו מצב מקבל לפי ההגדרה, הרי שהמכונה מקבלת את כל המילים ב-<math>L</math>, כלומר הראינו כי <math>L\subseteq L(M)</math>.
 
הכיוון השני קל להוכחה: אם מילה מסויימת <math>x</math> מתקבלת על-ידי האוטומט, אזי המצב <math>[x]</math> הוא מצב מקבל. נניח בשלילה ש<math>x\notin L</math> אזי קיימת מילה <math>y\in L</math> כך ש<math>[y]=[x]</math> (אחרת לא ייתכן ש<math>[x]</math> הוא מצב מקבל, בהתאם להגדרת המצבים המקבלים). אבל, זו סתירה, מכיוון שהמילה <math>z=\epsilon</math> הינה מילה מפרידה בין <math>x,y</math>, כי <math>yz\in L</math> ואילו <math>xz \notin L</math>. מכאן נובע כי <math>L(M)\subseteq L</math>.
 
לסיום, נראה שהמכונה הנ"ל הינה '''מינימלית''', כלומר בעלת מספר המצבים הקטן ביותר האפשרי.
לשם כך נעשה שימוש ביחס שקילות נוסף (בדומה למה שהוסבר בפסקה "הרעיון הכללי"). בהינתן אוטומט כלשהו <math>\ A</math>, היחס <math>\ R_A</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 \times A</math>, אזי יש בו רק מחלקת שקילות אחת! כלל שמספר מחלקות השקילות גדל, יש יותר אברים שנמצאים בשתי מחלקות שונות, ולכן היחס <math>R</math> יהיה תת-קבוצה קטנה יותר.]
 
האבחנה לפיה <math>\ R_A\subseteq R_L</math> נובעת מכך שאם <math>\ xR_A y</math> אז לאחר קריאת שתי המילים יגיע האוטומט <math>\ A</math> לאותו מצב, ועל כן לכל סיפא <math>\ z</math> שקורא האוטומט לאחר מכן הוא יגיע גם כן לאותו מצב. כלומר, האוטומט יחזיר תשובה זהה על <math>\ xz</math> ועל <math>\ yz</math> לכל <math>\ z</math>, ולכן <math>xR_Ly</math>, לפי הגדרה.