אוטומטים ושפות פורמליות/תכונות של שפות רגולריות/משפט מיהיל-נרוד: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←הוכחת המשפט: עיצוב |
מ ←הוכחת המשפט: עיצוב |
||
שורה 49:
{{טענה|שם=טענת עזר|תוכן=
לאחר עיבוד המילה <math>w</math>, האוטומט נמצא במצב <math>[w]</math>}}
{{הוכחה|
נוכיח באינדוקציה על אורך המילה <math>n</math>.
# בסיס: <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>.
| |||