תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←דוגמאות לשפות: הגהה |
מ ←כריעות: מחלקות של שפות ותכונותיהן: הרחבה |
||
שורה 15:
==כריעות: מחלקות של שפות ותכונותיהן==
נגדיר את מחלקות השפות הבאות:
{{הגדרה|תוכן=
<center>
<math>L \}</math> ניתנת להכרעה <math>R= \{ L \mid </math>
אם שפה L נמצאת בR, נאמר כי L היא שפה '''רקורסיבית'''.
<math>\}</math> קיימת מ"ט M ש<u>מקבלת</u> את כל המילים ב־L ו<u>אינה מקבלת</u> אף מילה שאינה ב־L (אבל לאו דווקא דוחה) <math>RE = \{ L \mid</math>
אם שפה L נמצאת בRE, נאמר כי L היא שפה '''נתנת למניה רקורסיבית'''.
<math>\}</math> קיימת מ"ט M ש<u>דוחה</u> את כל המילים שאינן ב־L ו<u>אינה דוחה</u> אף מילה ב־L (אבל לאו דווקא מקבלת) <math>coRE = \{ L \mid</math>
</center>
}}
נשים לב, אלו מחלקות של שפות, כלומר קבוצה של שפות שונות. כל קבוצה כזו מכילה אינסוף שפות שונות (וכל שפה כשלעצמה, מכילה מספר סופי או אינסופי של מילים).
{{טענה|
|