Question

p_np
proof

בהינתן שפה LL, נסמן ב LL^* את סגור קליני של השפה: כל המילים שהן שרשורים של מספר סופי של מילים מ-LL:

L={w1wk:w1,,wkL,kN} L^* = \{w_1 \cdots w_k : w_1,\ldots,w_k \in L, k \in \mathbb{N}\}

א. הוכיחו כי אם LNPL \in NP אז גם LNPL^* \in NP. הוכיחו את תשובתכם פעם אחת על ידי תיאור יחס מתאים ופעם נוספת על ידי תיאור מ"ט א"ד פולינומית מתאימה.

ב. הוכיחו כי אם LPL \in P אז גם LPL^* \in P.

1

Answers

א. נניח ש-MM מ"ט א"ד פולינומית שמכריעה את LL נבנה מ"ט א"ד MM^* שמכריעה את LL^* באופן הבא:

MM^* על קלט ww

  • מנחשת פירוק w1wkw_1 \dots w_k
  • בודקת ש-wiLw_i \in L לכל ii

נשים לב שאת הבדיקה עושים בטור ולא במקביל, כלומר קיים מסלול מקבל אמ"מ לכל ii wiLw_i \in L.

באופן דומה, אם RR יחס פולינומי וניתן לזיהוי פולינומי כך ש-LR=LL_R = L, נגדיר יחס R={(w,(w1,y1),(wk,yk)):w=w1wki  (wi,yi)R}R^* = \{(w, (w_1, y_1), \ldots (w_k, y_k)) : w = w_1 \dots w_k \land \forall i \; (w_i, y_i) \in R\} קל לראות שזהו יחס פולינומי שניתן לזיהוי פולינומי ו-LR=LL_{R^*} = L^*.

ב. כדי לדעת אם מילה w=s1skw = s_1\dots s_k שייכת ל-LL^*צריך לבדוק לכל 0ik0 \leq i \leq kאם מתקיים ש-s1siLs_1 \dots s_i \in L וגם si+1skLs_{i + 1} \dots s_k \in L^*. נשים לב שניתן לבדוק זאת באופן יעיל על ידי תכנון דינמי.

1
Feedback