תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ קישורים פנימיים |
מ ←תכונות מחלקות הכריעות: תיקון תבנית הוכחה |
||
שורה 120:
#<math>R=RE \cap coRE</math>}}
{{הוכחה|
קל לראות כי <math>R \subseteq RE\cap coRE</math> כי אם השפה ניתנת להכרעה, אז ברור שקיימת מכונה שרק דוחה או רק מקבלת.
שורה 132:
}}
{{הוכחה|
אם <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> כנדרש.
|