תורת החישוביות/כריעות שפות/משפט רייס/תרגילים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←מ״ט המבקרת בכל המצבים: הרחבה - העברת דוגמאות לתרגילים |
|||
שורה 1:
{{תורת החישוביות}}
==קבלת המחרוזת הריקה==
נגדיר
<math>L_\varepsilon = \{ \langle M \rangle \mid \varepsilon \in L(M)\}</math>. מהי התכונה המתאימה למשפט רייס? האם השפה רקורסיבית?
{{מוסתר|ta2 = right|הפתרון|2=
נגדיר את התכונה <math>S=\{ L\in RE \mid \varepsilon \in L\}</math>. S אינה טריוויאלית: <math>\Sigma^* \in S</math> ואילו <math>\emptyset \notin S</math> (וכאמור <math>\emptyset\in RE</math>). לפי משפט רייס <math>L_S \notin R</math>.
}}
==זיהוי שפה ריקה==
נגדיר
<math>L_\emptyset = \{ \langle M\rangle\mid L(M)=\emptyset\}</math> מהי התכונה המתאימה למשפט רייס? האם השפה רקורסיבית?
{{מוסתר|ta2 = right|הפתרון|2=
נגדיר את התכונה <math>S=\{\emptyset\}</math>, מכילה שפה אחת ולכן אינה טריוויאלית, ולפי המשפט <math>L_\emptyset \notin R</math>.
}}
==מ״ט המבקרת בכל המצבים==
| |||