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

# המילים <math>xz</math> ו-<math>yz</math> שתיהן אינן שייכות ל-<math>L</math>.

אם קיימת מילה <math>z</math> כך שאחת מהמילים בשפה והשניה אינה בשפה, נכנה את <math>z</math> '''מילה מפרידה''', ונובע ש-<math>x</math> ו-<math>y</math> אינן באותה מחלקת שקילות, <math> (x,y)\notin R_L</math>.

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

 

 

נוכיח שהאוטמט לעיל מקבל את השפה <math>L</math>. עובדה זו נובעת מטענת העזר הבאה:{{ש}}

{{הוכחה|

נוכיח באינדוקציה על אורך המילה <math>n</math>.