תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←כריעות: מחלקות של שפות ותכונותיהן: הרחבה - אטימולוגיה של רקורסיבית ונתנת למניה רקורסיבית |
|||
שורה 16:
נגדיר את מחלקות השפות הבאות:
{{הגדרה|תוכן=
1. <math>R</math> – קבוצת השפות ה'''כריעות''' (גם: '''ניתנות להכרעה''' או '''רקורסיביות''', '''R'''ecursive)
<center>
<math>L \}</math> ניתנת להכרעה <math>R= \{ L \mid </math>
<math>\}</math> קיימת מ"ט M ש<u>מקבלת</u> את כל המילים ב־L ו<u>אינה מקבלת</u> אף מילה שאינה ב־L (אבל לאו דווקא דוחה) <math>RE = \{ L \mid</math>▼
<math>\}</math> קיימת מ"ט M ש<u>דוחה</u> את כל המילים שאינן ב־L ו<u>אינה דוחה</u> אף מילה ב־L (אבל לאו דווקא מקבלת) <math>coRE = \{ L \mid</math>▼
</center>
2. <math>RE</math> – קבוצת השפות ה'''כריעות למחצה''' (גם: כריעות למחצה '''(לחיוב)''' או שפות הניתנות ל'''מניה רקורסיבית''', '''R'''ecursive '''E'''numerable)
▲<center><math>\ \}</math> קיימת מ"ט M ש<u>מקבלת</u> את כל המילים ב־L ו<u>אינה מקבלת</u> אף מילה שאינה ב־L (אבל לאו דווקא דוחה) <math>RE = \{ L \mid</math></center>
3. <math>coRE</math> – קבוצת השפות ה'''כריעות למחצה (לשלילה)'''
▲<center><math>\}</math> קיימת מ"ט M ש<u>דוחה</u> את כל המילים שאינן ב־L ו<u>אינה דוחה</u> אף מילה ב־L (אבל לאו דווקא מקבלת) <math>coRE = \{ L \mid</math></center>
}}
| |||