Question

rice

נאמר ששפה LL היא טריוויאלית אם L=L = \emptyset או L=ΣL = \Sigma^* ונאמר שתכונה SRES \subseteq RE היא טריוויאלית אם S=S = \emptyset או S=RES = RE

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

א. לכל זוג שפות לא טריוויאליות L1,L2RL_1,L_2 \in R מתקיים L1L2L_1 \leq L_2.

ב. לכל זוג תכונות לא טריוויאליות S1,S2RES_1,S_2 \subset RE מתקיים LS1LS2L_{S_1} \leq L_{S_2} (כזכור, LS={M:L(M)S}L_S = \{\langle M \rangle : L(M) \in S\})

ג. לכל זוג שפות L1,L2/REL_1,L_2 \notin RE מתקיים L1L2L_1 \leq L_2

1

Answers

א. נכון. מכיוון ש-L2L_2 לא טריוויאלית אז קיימות שתי מילים, xL2,y/L2x \in L_2, y \notin L_2. מכיוון ש-L1RL_1 \in R אז קיימת מ"ט שמכריעה אותה ולכן ניתן לבנות רדוקציה באופן הבא:

f(w)={xwL1yw/L1 f(w) = \begin{cases} x & w \in L_1 \\ y & w \notin L_1 \end{cases}

ב. לא נכון. אם נגדיר את S1S_1 להיות קבוצת השפות בנות 3 מילים לכל היותר, ואת S2S_2 להיות קבוצת השפות עם לפחות 3 מילים אז LS1=L3/REL_{S_1} = L_{\leq 3} \notin \text{RE} ו-LS2=L3REL_{S_2} = L_{\geq 3} \in \text{RE} ולכןLS1̸LS2L_{S_1} \not \leq L_{S_2}.

ג. לא נכון. משיקולי ספירה ישנם מספר לא בן מניה של שפות כאלו בעוד יש מספר בן מניה של רדוקציות. בין לכל שתי שפות שונות יש צורך ברדוקציה שונה ולכן אין מספיק רדוקציות.

1
Feedback