Question

הגדרה: עבור מחלקת שפות C , שפה L1 היא שלמה בC , אם היא שייכת לC , וכן לכל L2 L2 ∈ C ניתנת לרדוקציה ל L2 ≤ L1) L1)

הוכח או הפרך:

  • קיימת שפה שלמה בRE ∪ coRE.
  • קיימת שפה שלמה בcoRE.
  • קיימת שפה שלמה לקבוצת כל השפות P(Σ∗).
1

Answers

No answers yet ¯\_(ツ)_/¯
Feedback