תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
יצירה |
|||
שורה 22:
נשים לב, אלו מחלקות של שפות, כלומר קבוצה של שפות שונות. כל קבוצה כזו מכילה אינסוף שפות שונות (וכל שפה כלשעצמה, מכילה מספר סופי או אינסופי של מילים).
{{טענה|
תוכן=
#<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>.
}}
הוכחה לטענה 3:
אם <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> כנדרש.
[[קטגוריה:תורת החישוביות]]
| |||