» נושאי לימוד
» נושאי לימוד
יום שבת 4 באפריל 2020
בחן את עצמך
דף ראשי  תגבור  בחן את עצמך גרסה להדפסה

 בחן את עצמך

 

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

 

עבור כל אחת מהבניות הבאות, מלאו את הטבלה (הוכיחו או הביאו דוגמא נגדית)

 

             Extend(L) = { w | w=xy, xL, yΣ* }

             Prefix(L) = { w | xΣ* , wxL }

             Reverse(L) = { w | wRL }

             Rotate(L) = { xy | yxL }

             Swap(L) = {a1a2...ai-1aiai+1...an | a1a2...ai-1ai+1aiai+2...anL }

             Miss(L) = {a1a2...ai-1aiai+1...an | bΣ, b≠ai a1a2...ai-1bai+1...anL}

             Substring(L) = {w | x,yΣ*  xwyL }

             Exclude(L) = { w |   x,y,zΣ*  s.t.  w=xyz : yL }

             Half(L) = {w | xΣ*  |w|=|x| wxL }

 

 

הוכיחו כי הפונקציות הבאות הבאות פרימיטיביות-רקורסיביות :

 

f1(0)=1, f1(1)=2, f1(3)=3

f1(n)=f1(n-1)·f1(n-2)·f1(n-3)

 

החזקה הגדולה ביותר בפירוק  n לראשונייםf2(n) =

 

f3(0)=1

f3(x)=  f3(x/2)+1        if x is even

          f3((x-1)/2)-1    if x is odd

 

f4(i)= 4i   i=0,1,2,3,4,5

f4(i)= f4(i-2)+f5(i-3) + 4   i >5

 

f5(j)=5j  j=0,1,2,3,4,5

f5(j)= f5(j-3)*f4(j-2) + 5  j > 5

 

עבור כל אחת מהשפות הבאות, קבעו האם היא ב R, RE, CO-RE, או אף אחד מהנ"ל (הוכח תשובתך)

         (R – הכרעה, RE – קבלה, CO-RE – ההופכי ניתן לקבלה)

 

L1 = { ρ(M) | ρ(M) L(M) and ρ(M) ρ(M)L(M)

     L2= { ρ(M1) ρ(M2) | L(M1)L(M2) L(M1)L(M2) }

                                     L3= { ρ(M) | L(M)=Ĥ}     Ĥ=Hc

 

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