תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 8:
# השפה הריקה <math>\emptyset</math> – לכל קלט, המכונה עוברת בצעד החישוב הראשון ל־<math>q_{rej}</math>.
#כל שפה סופית <math>L=\{ a_1, a_2, \ldots, a_n \}</math> – נבדוק כל מילה אפשרית. מכיוון שכמות המילים סופית, נדרשים מספר סופי של מצבים (ובפרט, זו [[אוטומטים ושפות פורמליות/תכונות של שפות רגולריות|שפה רגולרית]])
# (כל שפה רגולרית – אוטומט סופי הוא מקרה פרטי של מכונת טיורינג, לכן מ"ט מסוגלת לחשב כל מה שאוטומט סופי יכול.)
# <math>\}</math> מספר האפסים בקלט שווה למספר האחדים <math>L=\{ x\in\{0,1\}^* \mid</math>. (זו שפה לא-רגולרית)
שורה 14:
{{-}}
==כריעות: מחלקות של שפות ותכונותיהן==
נגדיר את מחלקות השפות הבאות:
<center>
▲# (שפות רקורסיביות) <math>L \}</math> ניתנת להכרעה <math>R= \{ L \mid </math>
▲# (שפות נתנות למניה רקורסיבית) <math>\}</math> קיימת מ"ט M ש<u>מקבלת</u> את כל המילים ב־L ו<u>אינה מקבלת</u> אף מילה שאינה ב־L (אבל לאו דווקא דוחה) <math>RE = \{ L \mid</math>
</center>
נשים לב, אלו מחלקות של שפות, כלומר קבוצה של שפות שונות. כל קבוצה כזו מכילה אינסוף שפות שונות (וכל שפה כשלעצמה, מכילה מספר סופי או אינסופי של מילים).
שורה 74:
3. '''
:שייכות ל־RE: נריץ את M על x – אם המכונה תעצור, נקבל. אחרת – M לא עצרה וגם המכונה המסמלצת בלולאה אינסופית, ואינה מקבלת את הקלט הנ״ל.
מההגדרה, נובע עבור השפות המשלימות, <math>\overline{L_U}, \overline{L_D}, \overline{\text{
[[קטגוריה:תורת החישוביות]]
| |||