תורת החישוביות/כריעות שפות/תרגילים

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

סגירות RE לאיחוד בר-מניה[עריכה]

נניח קבוצה בת מניה של שפות , שכ״א מהן ב־RE. נניח שברשותנו פונקציה ברת־חישוב אשר לכל מספר טבעי מייצרת את .

נסמן את איחודן כ:

  1. מדוע אי אפשר להראות באינדוקציה ש־?
  2. הוכח כי .
  3. האם החיתוך של השפות, ב־RE ?

רמז לסעיף 2: נסה "לסמלץ" בבת אחת את כ״א מהשפות המרכיבות את .



שפה כריעה ניתנת למניה לקסיקוגרפית[עריכה]

עבור שפה כלשהי L, נאמר שמ״ט M מונה את המילים ב־L אם על קלט ריק M רושמת על סרט הזיכרון את כל המילים ב־L (ורק אותן). אם L שפה אינסופית, אזי כל מילה ב־L בהכרח תופיע על הסרט לאחר זמן סופי (M לעולם לא עוצרת, וממשיכה לרשום את כל המילים..)

הוכח: אם ורק אם קיימת מ״ט המונה את כל המילים ב־L לפי סדר לקסיקוגרפי