תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף

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