בחן את עצמך

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

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

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

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

             Reverse(L) = { w | w^R∊L }

             Rotate(L) = { xy | yx∊L }

             Swap(L) = {a₁a₂...a_i-1a_ia_i+1...a_n | a₁a₂...a_i-1a_i+1a_ia_i+2...a_n∊L }

             Miss(L) = {a₁a₂...a_i-1a_ia_i+1...a_n | b∊Σ, b≠a_i a₁a₂...a_i-1ba_i+1...a_n∊L}

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

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

             Half(L) = {w | x∊Σ*  |w|=|x| ⋀ wx∊L }

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

f₁(0)=1, f₁(1)=2, f₁(3)=3

f₁(n)=f₁(n-1)·f₁(n-2)·f₁(n-3)

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

f₃(0)=1

f₃(x)=  f₃(x/2)+1        if x is even

          f₃((x-1)/2)-1    if x is odd

f₄(i)= 4i   i=0,1,2,3,4,5

f₄(i)= f₄(i-2)+f₅(i-3) + 4   i >5

f₅(j)=5j  j=0,1,2,3,4,5

f₅(j)= f₅(j-3)*f₄(j-2) + 5  j > 5

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

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

L₁ = { ρ(M) | ρ(M) ∉L(M) and ρ(M) ρ(M)∊L(M)

     L₂= { ρ(M₁) ρ(M₂) | L(M₁)⋃L(M₂) ⊆L(M₁)⋂L(M₂) }

                                     L₃= { ρ(M) | L(M)=Ĥ}     Ĥ=H^c