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

תוכן שנמחק תוכן שנוסף
יעל י (שיחה | תרומות)
מ שוחזר מעריכה של 84.228.98.67 (שיחה) לעריכה האחרונה של Gran
שורה 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 LM</math> כנדרש.
}}