תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←כריעות: מחלקות של שפות: הגהה |
←כריעות: מחלקות של שפות: הרחבה |
||
שורה 10:
==כריעות: מחלקות של שפות ותכונותיהן==
נגדיר את מחלקות השפות הבאות:
<center>
שורה 25:
תוכן=
#<math>R \subseteq RE</math> , <math>R\subseteq coRE</math>
#<math>R=RE \cap coRE</math>}}
# <math>\ R</math> סגורה למשלים: אם <math>L \in R</math> אז גם השפה המשלימה, <math>\overline{L}\in R</math>.▼
הוכחה:
קל לראות כי <math>R \subseteq RE\cap coRE</math> כי אם השפה ניתנת להכרעה, אז ברור שקיימת מכונה שרק דוחה או רק מקבלת.
הכיוון השני: תהי <math>L \in RE\cap coRE </math>.{{ש}}
מכיוון ש־<math>L\in RE</math> קיימת מ"ט <math>M_1</math> שמקבלת כל מילה <math>x\in L</math> ולא מקבלת <math>x\in \overline L</math>. באופן דומה, מכיוון ש־<math>L\in coRE</math> קיימת מ"ט <math>M_2</math> שדוחה כל מילה <math>x\in \overline L</math> ולא דוחה אף <math>x\in L</math>.{{ש}}
נריץ את שתי המכונות במקביל (למשל ע״י שני סרטים): אם <math>M_1</math> מקבלת, נקבל; ואם <math>M_2</math> דוחה, נדחה (הראשון מביניהם). כל מילה <math>x</math> או שייכת או לא שייכת ל־<math>L</math> ולכן בהכרח אחד משני המקרים לעיל ייתרחש לאחר זמן סופי (כלומר, אם הקלט בשפה הוא בהכרח ייתקבל ע״י <math>M_1</math> לאחר זמן סופי, ואם הוא לא בשפה הוא יידחה ע״י <math>M_2</math> לאחר זמן סופי). לפיכך, המכונה שבנינו עוצרת על כל קלט אפשרי עם התשובה הנכונה.
{{טענה|תוכן=
▲
}}
הוכחה
אם <math>L\in R</math> אז קיימת מ"ט M המכריעה את L. נבנה מ"ט <math>\overline M</math> ע״י החלפת המצבים הסופיים: <math>q_{acc,M}=q_{rej,\overline M}</math> ו־<math>q_{rej,M}=q_{acc,\overline M}</math>.{{ש}}
<math>\overline M</math> עוצרת על כל קלט (כי <math>M</math> עוצרת על כל קלט), ובנוסף, <math>\overline M</math> עונה הפוך מ־<math>M</math>, כלומר <math>L(\overline M)= \overline M</math> כנדרש.
שורה 46 ⟵ 55:
:5.{{רווח קשיח|2}}<math>coRE</math> סגורה לאיחוד{{רווח קשיח|2}}
:6.{{רווח קשיח|2}}<math>R, RE, coRE</math> סגורות לחיתוך ושרשור{{רווח קשיח|2}}}}
(תרגיל: הוכח).
| |||