תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 31:
אם <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> כנדרש.
{{טענה|תוכן=
:4.{{רווח קשיח|2}}<math>R</math> סגורה לאיחוד:{{ש}}
::לכל <math>L_1, L_2 \in R</math> מתקיים <math>L_1 \cup L_2 \in R</math>{{רווח קשיח|2}}}}
הוכחה: תהי <math>M_1</math> מ"ט המכריעה את <math>L_1</math>, ותהי <math>M_2</math> מ"ט המכריעה את <math>L_2</math>.{{ש}}
נבנה מכונה M שמריצה את <math>M_1</math> ולאחר מכן את <math>M_2</math> (למשל, על סרט שני אליו מועתק הקלט בהתחלה). החזר "כן" אם אחת המכונות קיבלה, ואחרת - החזר "לא". נשים לב ששתי המכונות עוצרות על כל קלט ולכן גם M תעצור על כל קלט.
{{טענה|תוכן=
:5.{{רווח קשיח|2}}<math>RE</math> סגורה לאיחוד:{{ש}}
::לכל <math>L_1, L_2 \in RE</math> מתקיים <math>L_1 \cup L_2 \in RE</math>{{רווח קשיח|2}}}}
ההוכחה לעיל אינה מספיק טוב, מכיוון שייתכן ש־<math>M_1</math> אינה עוצרת, ולכן לעולם לא נגיע לשלב בו אנחנו מריצים את <math>M_2</math>. במילים אחרות, אסור לנו להריץ את שתי המכונות בטור, וצריך להריץ אותן בצורה מקבילה, כל אחת על סרט אחר. מסמלצים צעד מ־<math>M_1</math> ולאחריו צעד של <math>M_2</math> וחוזר חלילה. אם אחת המכונות קיבלה – עוצרים ומקבלים. אם שתיהם בלולאה אינסופים, גם המכונה שבנינו לא תעצור (אך זה מותר עבור קלט שאינו בשפה, לפי הגדרת <math>\ RE</math>.
{{טענה|תוכן=
:5.{{רווח קשיח|2}}<math>coRE</math> סגורה לאיחוד{{רווח קשיח|2}}
:6.{{רווח קשיח|2}}<math>R, RE, coRE</math> סגורות לחיתוך ושרשור{{רווח קשיח|2}}}}
[[קטגוריה:תורת החישוביות]]
| |||