Question

winter17-18
misc

עבור שפות, L1,L2L_1, L_2, נגדיר את ההפרש הסימטרי שלהן, L1L2L_1 \triangle L_2, כאוסף המילים xx כך ש-xL1L2x \in L_1 \setminus L_2 או xL2L1x \in L_2 \setminus L_1 (כלומר אוסף המילים ששייכות בדיוק לאחת מבין שתי השפות L1,L2L_1, L_2).

עבור אוסף מכונות C={M1,M2,}C = \{\langle M_1 \rangle, \langle M_2 \rangle, \ldots \} המכיל לפחות שני קידודים של מכונות, נאמר ש-DD מבחין של CC אם לכל שתי מכונות M1,M2C\langle M_1 \rangle, \langle M_2 \rangle \in C מתקיים D(M1,M2)=xD(\langle M_1 \rangle, \langle M_2 \rangle) = x כך ש-xL(M1)L(M2)x \in L(M_1) \triangle L(M_2), אם קיים כזה, ואחרת DD לא עוצרת.

בכל אחד מהסעיפים הבאים קבעו האם קיים מבחין DD לכל אוסף מכונות CC המקיים את התנאים בסעיף:

  1. CC אוסף קידודי מכונות כלשהו.
  2. CC המקיימת שלכל MC\langle M \rangle \in C, MM מכריעה את השפה L(M)L(M).
2

Answers

1. נניח בשלילה שקיים מבחין כזה' DD ונתאר מ"ט, MM, שמקבלת את LEQ\overline{L_{EQ}}.

MM על קלט M1,M2\langle M_1 \rangle, \langle M_2 \rangle:

  • מריצה את DD על M1,M2\langle M_1 \rangle, \langle M_2 \rangle ומקבלת אמ"מ DD עצר.

קל לראות ש-MM אכן מקבלת את LEQ\overline{L_{EQ}}, מכיוון שלא קיימת מ"ט שמקבלת את LEQ\overline{L_{EQ}} אז לא קיים מבחין כנדרש.

2. נתאר מבחין, DD על קלט (M1,M2)(\langle M_1 \rangle, \langle M_2 \rangle):

  • מריץ את M1M_1 ו-M2M_2 על כל xx לפי סדר לקסיקוגרפי
  • פולט xx אם אחת המכונות קיבלה והשנייה דחתה

נשים לב שמכיוון שמובטח לנו שב-CC רק מכונות שעוצרות אז אם קיים xx כנדרש נמצא אותו בשלב מסוים ואם לא קיים כזה אז DD לא יעצור כנדרש.

1
Feedback