הועלה לאתר:  
מספר עמודים: 32
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת החישוביות - חלק ראשון

סיכום מאת: ניר אדר

4. בעיות הכרעה

הגדרה: שפה L מעל א"ב plot:\[\Sigma \] היא קבוצה plot:\[L \subseteq {\Sigma ^*}\].

הגדרה: מ"ט לזיהוי שפות או בשם נוסף, מ"ט לקבלת שפות, היא מ"ט רגילה שבה: מוגדר plot:\[F = \left\{ {{q_A},{q_R}} \right\}\] (A מסמל accept ו-R מסמן reject). נאמר שמ"ט M כנ"ל מקבלת קלט X, אם M עוצרת עבור הקלט X במצב plot:\[{q_A}\], ונאמר שמ"ט כנ"ל דוחה קלט X, אם המכונה M עוצרת עבור הקלט X במצב plot:\[{q_R}\].

אבחנה: ייתכן שהחישוב של M על קלט X אינו מסתיים, ולכן "לא מקבלת" אינו זהה ל"דוחה" וכן "לא דוחה" אינו זהה ל"מקבלת".

הגדרה: השפה של מכונה תוגדר כך:  {M מקבלת את x|x} L(M) =.

הגדרה: אם M עוצרת לכל קלט, אומרים ש-M מכריעה את השפה L(M). כלומר, שלכל plot:\[x \in L\] המכונה M עוצרת ב-plot:\[{q_A}\] ולכל plot:\[x \notin L\] המכונה עוצרת ב-plot:\[{q_R}\].

דוגמאות לשפות שניתנות להכרעה:

  • plot:\[{\Sigma ^*}\]: מ"ט שבצעד הראשון, ללא תלות בקלט, עוברת ל-plot:\[{q_A}\], היא מ"ט המכריעה את plot:\[{\Sigma ^*}\].
  • plot:\[\Phi \]: מ"ט שבצעד הראשון, ללא תלות בקלט, עוברת ל-plot:\[{q_R}\], היא מ"ט המכריעה את plot:\[\Phi \].

הגדרה: נקבע את הא"ב שלנו להיות plot:\[\Sigma  = \left\{ {0,1} \right\}\].

נגדיר את קבוצות השפות הבאות (מחלקות השפות):

  • { L ניתנת להכרעה |L } plot:\[ \triangleq \]R.
  • { קיימת מ"ט שמקבלת את L| L} plot:\[ \triangleq \] RE.
  • plot:\[{\text{CO - RE}} = \left\{ {L|\overline L  \in RE} \right\}\] כאשר plot:\[\overline L  \triangleq {\Sigma ^*}\backslash L\]. כלומר, קבוצת כל השפות עבורן קיימת מ"ט M שלכל קלט שאינו בשפה – היא דוחה, ולכל קלט שבשפה – היא מקבלת או לא עוצרת.

שפה L השייכת ל-R נקראת שפה רקורסיבית. שפה L השייכת ל-RE מכונה שפה הניתנת למניה רקורסיבית.



אבחנות: plot:\[{\text{R}} = {\text{RE}} \cap {\text{CO - RE}},{\text{ R}} \subseteq {\text{CO - RE}},{\text{ R}} \subseteq {\text{RE}}\]

תכונות של המחלקות:

1.       R סגורה למשלים: plot:\[L \in {\text{R}} \Rightarrow \overline L  \in {\text{R}}\] (נשים לב כי RE לא סגורה למשלים!).

2.       R סגורה לאיחוד: plot:\[{L_1},{L_2} \in {\text{R}} \Rightarrow {L_1} \cup {L_2} \in {\text{R}}\].

3.       R ו-RE סגורות לחיתוך plot:\[{L_1},{L_2} \in {\text{R}} \Rightarrow {L_1} \cap {L_2} \in {\text{R}}\].

4.       R ו-RE סגורות לשרשור.

מבחר הוכחות:

R סגורה למשלים – תהי plot:\[L \in {\text{R}}\], אזי קיימת מ"ט M המכריעה את L. נבנה מ"ט plot:\[\overline M \] עבור השפה plot:\[\overline L \] בצורה הבאה: plot:\[\overline M \] זהה ל-M, למעט: plot:\[\overline {{q_R}}  = {q_A},\,\,\overline {{q_A}}  = {q_R}\]. מתקיים כי plot:\[\overline M \] עוצרת תמיד, וכן כי plot:\[L\left( {\overline M } \right) = \overline L \]. מכאן plot:\[\overline M \] מכריעה את plot:\[\overline L \], ולכן plot:\[\overline L  \in {\text{R}}\].

R סגורה לאיחוד – רעיון ההוכחה הוא לבנות מ"ט M בעלת 2 ראשים המכריעה את plot:\[{L_1} \cup {L_2}\]. נעתיק את X מילת הקלט לסרט הראשון, ונפעיל עליה את plot:\[{M_1}\]. אם plot:\[{M_1}\] מקבלת, נקבל. אחרת, נעתיק את X לסרט השני ונפעיל עליו את plot:\[{M_2}\]. אם plot:\[{M_2}\] מקבלת, נקבל, אחרת – נדחה. מתקיים כי M עוצרת תמיד, וכי M מקבלת קלט X אמ"מ plot:\[X \in {L_1} \cup {L_2}\], ולכן plot:\[{L_1} \cup {L_2} \in {\text{R}}\].

טענה

RE סגורה לאיחוד

רעיון ההוכחה דומה להוכחה לגבי R.

נשים לב שלא ניתן לבצע בדיוק את אותה הוכחה, מכיוון שחישוב מכונה לא מסתיים תמיד. לפיכך נעבוד עם מכונה בעלת שני סרטים, שתעשה צעד אחד על סרט 1 כמו plot:\[{M_1}\] ולאחריו צעד על סרט 2 כמו plot:\[{M_2}\]. במידה ואחת המכונות עוצרת, אזי גם המכונה בעלת שני הסרטים תעצור.

ניתן להוכיח כי השפה אותה מקבלת מכונה זו היא איחוד שתי השפות.



תגיות המסמך:

לפרק הקודם3. מכונה אוניברסלית
לפרק הבא4.1. דוגמאות לשפות במחלקות
מאת: דנה

החלק הראשון

בבקשה
מאת: אני

http://www.underwar.co.il/download.asp?ID=407
http://www.underwar.co.il/download.asp?ID=299
מאת: רועי

אני חייב את המסמך הזה...הצילו

מאת: חשוון

מתי המסמך יחזור?
שיתוף:
| עוד