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

תוכן שנמחק תוכן שנוסף
הוספת "{" חסר בהגדרת שפת האלכסון, דוגמא 2
Shomsky (שיחה | תרומות)
מאין תקציר עריכה
שורה 117:
{{הוכחה|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 ML</math> כנדרש.
}}
 
שורה 129:
: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>).
 
{{טענה|תוכן=