אוטומטים ושפות פורמליות/תכונות של שפות רגולריות/משפט מיהיל-נרוד: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
המשפט |
←משפט מיהיל-נרוד: הוכחת כיווון אחד |
||
שורה 36:
תוכן=מספר המצבים המינימלי באוטומט סופי דטרמיניסטי אשר מקבל את L הוא כמספר מחלקות השקילות של <math>\ R_L</math>}}
כתוצאה ממשפט זה, אם קיימות אינסוף מחלקות שקילות, אזי לא קיים אוטומט סופי המקבל את L, כלומר, במקרה זה L היא שפה לא-רגולרית.
=== הוכחת המשפט ===
עבור שפה L נבנה א"ד המקבל אותה, כאשר המצבים של האוטומט יהיו מחלקות השקילות השונות. נסמן ב<math>[x]</math> את מחלקת השקילות המכילה את המילה <math>x</math> (ייתכנו סימונים נוספים לאותה מחלקה, למשל, אם המילה y באותה מחלקת שקילות, אזי <math>[y]</math> מתייחס לאותה מחלקת שקילות.
האוטומט מוגדר באופן הבא:
* מצבי האוטומט הינם מחלקות השקילות השונות של L
* המצב ההתחלתי הינו <math>[\epsilon]</math>
* פונקציית המעברים מוגדרת על ידי <math>\delta([x],a)=[xa]</math>, לכל אות <math>a\in \Sigma</math> ולכל מחלקת שקילות <math>[x]\in Q</math>. חשוב לציין כי פונקציה זו מוגדרת היטב מכיוון שמדובר במחלקות שקילות. לא ייתכן ששתי מילים <math>x,y</math> נמצאות באותה מחלקת שקילות, ואילו בשרשור אות נוספת <math>z</math> נקבל שתי מחלקות שקילות שונות <math>[xz]\ne[yz]</math>, מכיוון שאם כך, הרי <math>z</math> הינה '''מילה מפרידה''', ולא ייתכן ש<math>x,y</math> שייכות לאותה מחלקת שקילות.
* מצב מקבל הוא כל מצב <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> על פי הגדרתה, ולכן הטענה מתקיימת.
# צעד: נניח כי טענת העזר מתקיימת עבור מילים באורך <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>.
| |||