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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
←‏הוכחת המשפט: מינמליות, מבוסס על ויקיפדיה.
Gran (שיחה | תרומות)
מ ניוט, קטגוריה.
שורה 1:
{{אוטומטים ושפות פורמליות}}
בפרק הקודם, [[../למת הניפוח לשפות רגולריות/]], ראינו כי לאוטומט סופי יש מגבלה - כמות המצבים הסופית - אשר גורמת לשפה הרגולרית להיות בעלת מבנה. משפט מיהיל-נרוד (Myhill-Nerode) מכליל רעיון זה, ומאפשר לנו הבנה טובה יותר של הקשר בין השפה אל האוטומט שמזהה אותה.
 
שורה 63 ⟵ 64:
 
האבחנה לפיה <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>, לפי הגדרה.
 
 
 
 
{{אוטומטים ושפות פורמליות|מוגבל}}
 
[[קטגוריה:אוטומטים ושפות פורמליות|מבוא]]