תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ הגהה |
|||
שורה 14:
{{-}}
==כריעות: מחלקות של שפות ותכונותיהן==
נגדיר את מחלקות השפות הבאות:▼
<math>L \}</math> ניתנת להכרעה <math>R= \{ L \mid </math>▼
{{הגדרה|תוכן=
<math>\}</math> קיימת מ"ט M ש<u>מקבלת</u> את כל המילים ב־L ו<u>אינה מקבלת</u> אף מילה שאינה ב־L (אבל לאו דווקא דוחה) <math>RE = \{ L \mid</math>▼
▲נגדיר את מחלקות השפות הבאות:
▲# (שפות רקורסיביות) <math>L \}</math> ניתנת להכרעה <math>R= \{ L \mid </math>
<math>\}</math> קיימת מ"ט M ש<u>דוחה</u> את כל המילים שאינן ב־L ו<u>אינה דוחה</u> אף מילה ב־L (אבל לאו דווקא מקבלת) <math>coRE = \{ 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>
}}
נשים לב, אלו מחלקות של שפות, כלומר קבוצה של שפות שונות. כל קבוצה כזו מכילה אינסוף שפות שונות (וכל שפה כשלעצמה, מכילה מספר סופי או אינסופי של מילים).
| |||