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

תוכן שנמחק תוכן שנוסף
MrOklein (שיחה | תרומות)
שורה 53:
# בסיס: <math>n=0</math>, המכונה מתחילה במצב <math>[\epsilon]</math> על פי הגדרתה, ולכן הטענה מתקיימת.
# צעד: נניח כי טענת העזר מתקיימת עבור מילים באורך <math>n=k</math>, ונראה כי מתקיימת למילים באורך <math>n=k+1</math>. תהי המילה <math>w=w_1w_2\ldots w_kw_{k+1}</math> קלט האוטומט. לפי הנחת האינדוקציה, לאחר עיבוד <math>w_1\ldots w_k</math> המכונה נמצאת במצב <math>[w_1\ldots w_k]</math>, כעת מתבצע המעבר <math>\delta([w_1\ldots w_k],w_{k+1}) </math> שעל-פי הגדרת האוטומט מוביל את המכונה למצב <math>[w]</math> כנדרש.}}
מכיוון שכל מילה <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>.