» נושאי לימוד
» נושאי לימוד
יום ראשון 5 ביולי 2020
שאלות חזרה
דף ראשי  רדוקציות  שאלות חזרה גרסה להדפסה

      שאלות חזרה

 

נניח שקיים סרט קלט המייצג את המערך In[ ]  , מערך אינסופי.

התוכנית הבאה מחשבת את מספר האיברים השונים מ- # במערך :

              1)Sum=0

             2)X=1

             3)If In[X]==0 goto 7

             4)Sum=Sum+1

             5)X=X+1

             6)goto 3

             7)end

כתבו את טבלת המעברים השקולה לפרוצדורה הנ"ל.

 

פתרון:

S(#,#)            q1(L,R)

q1(1, #)         q1(L, #)

q1(#,#)          q1(L, #)

q1($,#)         q2(R, #)

q2(1, #)         q3(1,1)

q3(1,1)         q3(R,R)

q3(1, #)        q3(R, #)

q3(#,#)         q2(R, #)

q2(#,#)           q4(L,L)

q4(1,1)           q4(#,1)

q4(#,1)          q4(L,1)

q4($,1)         q5(1, #)

q4($,#)            h(#,#)

q5(1, #)        q6(R,L)

q6(#,1)        q5(1, #)

q6(#,#)          h(#,R)

 

קבע האם השפה:

{ב- L(P) יש מילים מאורך זוגי בלבד | P }= Heven

ניתנת להכרעה:

 

פתרון:

טענה: Heven אינה ניתנת להכרעה.

הוכחה: ברדוקציה הפוכה מ-H .

*Σ1={(P,w)|P is a program, w is a string} > H

*Σ2= {Q| Q is a program} > Heven

נבנה רדוקציה f:Σ1*→Σ2* , כך שבהינתן זוג (P,w)  מוציאה

f(P,w)=Q, כך ש- (P,w) שייכת ל-H אמ"ם Q לא שייכת ל-Heven.

            Q(x)

            {

               P(w);

                Return;

             }

מתקיים:

 אם P(w) עוצרת אזי Q עוצרת לכל קלט, בפרט גם לקלטים באורך אי-זוגי, כלומר Q לא שייכת ל- Heven.

אם P(w) לא עוצרת, אזי Q לא עוצרת לכל קלט. בפרט, כל הקלטים שעבורם Q עוצרת הינם באורך אי זוגי, כלומר Q שייכת ל-Heven.

כלומר (P,w) שייכת ל-H אמ"ם Q לא שייכת ל- Heven.

 

 25-01-04 / 12:02  עודכן ,  22-01-04 / 21:25  נוצר ע"י שמרית דויטש  בתאריך 
 מסקנות - הקודםהבא - שאלות חזרה- המשך 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 7