תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
הוספת "{" חסר בהגדרת שפת האלכסון, דוגמא 2 |
מאין תקציר עריכה |
||
שורה 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
}}
שורה 129:
:5.{{רווח קשיח|2}}<math>RE</math> סגורה לאיחוד:{{ש}}
::לכל <math>L_1, L_2 \in RE</math> מתקיים <math>L_1 \cup L_2 \in RE</math>{{רווח קשיח|2}}}}
ההוכחה לעיל אינה מספיק
{{טענה|תוכן=
|