Question

classification_r_re

עבור כל אחת מהשפות הבאות קבעו האם היא שייכת ל-RR והאם היא שייכת ל-RERE:

}\}קיימת מ"ט MM' כך ש-MM' מקבלת את xx או ש-MM מקבלת את M\langle M' \rangle : L1={(M,x)L_1 = \{(\langle M \rangle, x)

}\}קיימת מ"ט MM' כך ש-MM' מקבלת את xx וגם MM מקבלת את M\langle M' \rangle : L2={(M,x)L_2 = \{(\langle M \rangle, x)

}\}לכל מ"ט MM' ,MM' מקבלת את xx או ש-MM מקבלת את M\langle M' \rangle : L3={(M,x)L_3 = \{(\langle M \rangle, x)

}\}לכל מ"ט MM' ,MM' מקבלת את xx וגם MM מקבלת את M\langle M' \rangle : L4={(M,x)L_4 = \{(\langle M \rangle, x)

1

Answers

1. נשים לב שלכל xx קיימת מ"ט שמקבלת אותו (למשל המ"ט שמקבלת הכל) ולכן L1=ΣRL_1 = \Sigma^* \in \text{R}.

2. נראה ש-L2RERL_2 \in \text{RE} \setminus \text{R}.

שייכות ל-RE:

לכל מחרוזת MΣ\langle M' \rangle \in \Sigma^* נריץ את MM על M\langle M' \rangle ואת MM' על xx ונקבל אמ"מ שתי ההרצות הנ"ל הסתיימו בקבלה.

נראה ש-L2RL_2 \notin \text{R} על ידי רדוקציה מ-HP:

f(M,x)=(Mx,ε)f(\langle M \rangle, x) = (M_x, \varepsilon)

כאשר MxM_x על קלט ww:

  • מריצה את MM על xx
  • מקבלת

נשים לב ש-

L(Mx)={ΣM halts on xotherwise L(M_x) = \begin{cases} \Sigma^* & M \text{ halts on } x \\ \emptyset & \text{otherwise} \end{cases}

ולכן (M,x)HP(Mx,ε)L2(\langle M \rangle, x) \in \text{HP} \iff (M_x, \varepsilon) \in L_2.

3. נראה ש-L3REL_3 \notin \text{RE} על ידי רדוקציה מ-HP\overline{HP}:

f(M,x)=(Mx,ε)f(\langle M \rangle, x) = (M_x, \varepsilon)

כאשר MxM_x על קלט ww

  • מריצה את MM על xx במשך w|w| צעדים לכל היותר
  • אם MM עצרה דוחה ואחרת מקבלת

נשים לב ש:

L(Mx)={ΣkM halts on x in k stepsΣotherwise L(M_x) = \begin{cases} \Sigma^k & M \text{ halts on } x \text{ in k steps} \\ \Sigma^* & \text{otherwise} \end{cases}

כלומר אם MM לא עוצרת על xx אז (Mx,ε)L3(M_x, \varepsilon) \in L_3. מצד שני אם MM עוצרת על xx תוך kk צעדים אז MxM_x דוחה כל מ"ט שהקידוד שלה ארוך מ-kk בפרט מ"ט עם קידוד ארוך שדוחה את ε\varepsilon.

4. נשים לב שלא משנה מהוא xx קיימת מ"ט שדוחה אותו ולכן L4=RL_4 = \emptyset \in \text{R}.

2
Feedback