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

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

נניח קבוצה בת מניה של שפות $L_1,L_2,\dots$, שכ״א מהן ב־RE. נניח שברשותנו פונקציה בת־חישוב $f$ אשר לכל מספר טבעי $i$ מייצרת את $⟨M_i⟩$.

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

$L=\bigcup _{i=1,2,\dots }{L}_i.$

1. מדוע אי אפשר להראות באינדוקציה ש־$L\in RE$?
2. הוכח כי $L\in RE$.
3. האם החיתוך של השפות, $\bigcap _{i=1,2,\dots }{L}_i.$ ב־RE ?

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

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

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

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