Υπολογιστική Πολυπλοκότητα — Ιανουάριος 2023 — Θέμα (2 μονάδες)¶
Μεταγραφή της φωτογραφίας image0.jpg (Θέμα Ιανουάριος '23).
image0.jpg¶
Θέμα Ιανουάριος '23 (2 μονάδες)
Έστω η αιτιοκρατική ΤΜ \(M\) όπου \(\Sigma = \{0,1\}\) και \(\Gamma = \{0,1,\sqcup\}\) με την διπλανή συνάρτηση μετάβασης. Έστω ότι η αρχική κατάσταση είναι η \(q_0\), η κατάσταση απόρριψης είναι η \(q_r\) και η κατάσταση αποδοχής είναι η \(q_\alpha\). Είναι η \(M\) διαγνώστης; Ποια είναι η γλώσσα που αναγνωρίζει η \(M\); Αιτιολογήστε την απάντησή σας.
(Α: Αριστερά, Δ: Δεξιά)
[Σχήμα: διάγραμμα καταστάσεων της TM \(M\) με καταστάσεις \(q_0\), \(q_1\), \(q_2\), \(q_\alpha\) και δύο καταστάσεις με ετικέτα \(q_r\). Μεταβάσεις: \(q_0 \to q_1\) με \(1\to\Delta\); \(q_0 \to q_r\) (κάτω) με \(\sqcup,0\to\Delta\); \(q_1 \to q_r\) (πάνω δεξιά) με \(0\to\Delta\); \(q_1 \to q_2\) με \(1\to\Delta\); \(q_1 \to q_0\) (καμπύλο βέλος) με \(\sqcup\to 1,\mathrm{A}\); \(q_2 \to q_0\) με \(\sqcup\to 1,\mathrm{A}\); \(q_2 \to q_r\) με \(0\to\Delta\); \(q_2 \to q_\alpha\) με \(1\to\Delta\).]
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2023-01.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):20230316_142950.jpg
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: χειρόγραφη λύση φοιτητή (φωτογραφία 20230316_142950.jpg)
Προσοχή
Η λύση καλύπτει μόνο το θέμα των 2 μονάδων της φωτογραφίας image0.jpg. Η εκφώνηση δεν φαίνεται στη φωτογραφία λύσης. Στο Discord (9/6/2023) αναφέρθηκε ότι υπάρχουν ενδεικτικές λύσεις του θέματος Ιανουαρίου, που όμως δεν βρίσκονται στον φάκελο. Αν βρεθούν, θα πρέπει να αντικαταστήσουν αυτή τη λύση φοιτητή.
Λύσεις — Υπολογιστική Πολυπλοκότητα — Ιανουάριος 2023¶
Χειρόγραφη λύση φοιτητή για το θέμα των 2 μονάδων. Η μεταγραφή ακολουθεί τη φωτογραφία.
20230316_142950.jpg¶
Θέμα Ιανουάριος '23
→ αιτιοκρατική TM → δεν έχει [δυσανάγνωστο] ταυτόχρονα
αν το τρέχω για είσοδο 0 → q_r, που σημαίνει ότι η γλώσσα δεν περιέχει 0 [σημείωση πάνω από το βέλος: «και ⊔»]
q_0 11 > 1q_1 1 > 11q_2 > 1q_0 11 > 11q_1 1 > 111q_2 > 11q_0 11
[σημείωση: «για είσοδο 1»] Εγκλωβίζεται άρα δεν είναι διαγνώσιμη.
111 → accept
..., 000, 00, 0, ε → reject
1, 11 → εγκλωβίζεται
Σ = 111(0+1)*
[κείμενο κομμένο στο κάτω άκρο της φωτογραφίας: «ο τρόπος που διαβάζω…»]
Σημείωση: χειρόγραφη λύση του φοιτητή· το κείμενο της εκφώνησης δεν φαίνεται στη φωτογραφία.