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

תוכן שנמחק תוכן שנוסף
שורה 58:
 
לסיום, נראה שהמכונה הנ"ל הינה '''מינימלית''', כלומר בעלת מספר המצבים הקטן ביותר האפשרי.
לשם כך נעשה שימוש ביחס שקילות נוסף (בדומה למה שהוסבר בפסקה "הרעיון הכללי"). בהינתן אוטומט כלשהו <math>\ A</math>, היחס <math>\ R_A</math> המוגדר מעל <math>\ \Sigma^*</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> יהיה תת-קבוצה קטנה יותר.]