Question

r_re
proof

הוכיחו/הפריכו את הטענות הבאות:

א. אם L1RERL_1 \in RE \setminus R וגם L2coRERL_2 \in coRE \setminus R אז L1L2/RL_1 \cup L_2 \notin R

ב. אם L1REL_1 \in RE וגם L2coREL_2 \in coRE אז L1L2RL_1 \cap L_2 \in R

ג. אם L1RERL_1 \in RE \setminus R וגם L2RERL_2 \in RE \setminus R אז L1L2/RL_1 \cup L_2 \notin R

הערה: בסעיף זה, במידה ומציגים שפה LRERL \in RE \setminus R, אין צורך להוכיח את הסיווג של LL, מספיק לנמק בקצרה.

ד. אם L1/RL_1 \notin R ו- L2L_2 שפה סופית אז L1L2/RL_1 \cup L_2 \notin R

1

Answers

א. לא נכון, למשל L3L_{\geq 3} ו-L3L_{\leq 3}.

ב. לא נכון, למשל L3L_{\geq 3} ו-L3L_{\leq 3}.

ג. לא נכון, למשל

L1={(0M):ML(M)}{1M}L_1 = \{(0\langle M \rangle) : \langle M \rangle \in L(M)\} \cup \{1\langle M \rangle\}

ו-

L2={(1M):ML(M)}{0M}L_2 = \{(1\langle M \rangle) : \langle M \rangle \in L(M)\} \cup \{0\langle M \rangle\}

ד. נכון. נניח בשלילה ש-L1L2RL_1 \cup L_2 \in \text{R} אז קיימת מ"ט שמכריעה אותה, M12M_{1 \cup 2}. כמו כן, מכיוון ש-L2L1L_2 \setminus L_1 סופית אז קיימת מ"ט שמכריעה גם אותה, M21M_{2 \setminus 1}.

נתאר מ"ט שמכריעה את L1L_1, MM.

כאשר, MM על קלט xx:

  • מריצה את M12M_{1 \cup 2} על xx ואם דוחה אז דוחה גם כן.
  • מריצה את M12M_{1 \setminus 2} על xx ועונה הפוך ממנה.

קל לראות ש-MM אכן מכריעה את L1L_1 - סתירה.

1
Feedback