Γλώσσες αποφασίσιμες και αποδεκτές

A)
 Μπορείτε να βρείτε πέντε γλώσσες L1, L2, L3, L4 και L5
 έτσι ώστε L1 υποσύνολο  L2,L3,L4 υποσύνολο  L5
και επιπλέον οι γλώσσες L1, L2, και L5 να είναι αποφασίσιμες, η L3 να είναι αποδεκτή
αλλά όχι αποφασίσιμη και η L4 να είναι μη αποδεκτή; Θεωρείστε ότι Li
 υποσύνολο  {0,1}*, 1 ≤ i ≤ 5.

(Β)
 Έστω οι δύο παρακάτω γλώσσες:
1.  L1 = {: Η Μ δεν αποδέχεται καμία λέξη περιττού μήκους} 
2.  L2 = {: Η L(Μ) είναι Turing αποδεκτή} 
Β1) Χρησιμοποιήστε το Θεώρημα του Rice (αν δεν είναι δυνατό να το εφαρμόσετε
να  αναφέρετε  γιατί)  και  στις  δύο  γλώσσες  ώστε  να  αποδείξετε  την  μη
αποφασισιμότητά τους.
Β2) Αποδείξτε ότι η γλώσσα L1 είναι μη αποδεκτή (χρησιμοποιείστε την περίπτωση
(δ) του Θεωρήματος 2.4  καθώς  και  τη  μεθοδολογία  που  αναπτύσσεται  στην
απόδειξη  του  Θεωρήματος 2.11  του  Τόμου  Β). Να κάνετε την αναγωγή από το
συμπλήρωμα  της  γλώσσας  τερματισμού HALT  =  {: η Turing  μηχανή  M 
τερματίζει με είσοδο w}.
Β3) Αποδείξτε ότι η γλώσσα L2 είναι αποδεκτή δίνοντας μια Τuring μηχανή που να
την αποδέχεται.