תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←משפט רייס: תקלדה |
|||
שורה 65:
==מניה רקורסיבית של שפות בעלות תכונה==
{{בעבודה}}▼
בחלק הקודם ראינו שאם התכונה <math>S</math> איננה טריוויאלית, אז שאלת השייכות ל-<math>L_S</math> איננה ב-<math>R</math>. בחלק זה נעסוק בשאלה מהם התנאים ל-<math>S</math> כך ששאלת השייכות ל-<math>L_S</math> תהיה ב-<math>RE</math>.
עם זאת, ישנם תנאים נוספים ל-<math>S</math>, שקיומם מהווה תנאי מספיק והכרחי לכך ששאלת השייכות היא ב-<math>RE</math>.
▲{{בעבודה}}
{{משפט|תוכן=
בהנתן תכונה <math>S \subseteq RE</math>, אז <math>LS \in RE</math> אמ"ם מתקיימות כ"א מהתכונות הבאות:
# אם <math>L_1 \in S</math>, וכן <math>L_1, L_2 \in RE</math>, וכן <math>L_1 \subseteq L_2</math>, אז <math>L_2 \in S</math>.
# אם <math>L_1 \in S</math>, אז יש ל-<math>L_2</math> תת-שפה סופית <math>L_2 \subseteq L_1</math> המקיימת <math>L_2 \in S</math>.
# שפת כל השפות הסופיות ב-<math>S</math> היא ב-<math>RE</math> (כלומר, יש מ"ט המונה כל שפה סופית ב-<math>S</math>).
}}
==דוגמאות ליישומים==
| |||