אוטומטים ושפות פורמליות/תכונות של שפות רגולריות/משפט מיהיל-נרוד: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←משפט מיהיל-נרוד: הוכחת כיווון אחד |
מ ←הוכחת המשפט: עיצוב |
||
שורה 46:
* מצב מקבל הוא כל מצב <math>[x]</math> עבור מילה בשפה, <math>x\in L</math>.
נוכיח שהאוטמט לעיל מקבל את השפה <math>L</math>.
{{טענה|שם=טענת עזר|תוכן=
לאחר עיבוד המילה <math>w</math>, האוטומט נמצא במצב <math>[w]</math>
נוכיח באינדוקציה על אורך המילה <math>n</math>.
# בסיס: <math>n=0</math>, המכונה מתחילה במצב <math>[\epsilon]</math> על פי הגדרתה, ולכן הטענה מתקיימת.
| |||