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