Θεωρία Υπολογισμού και Πολυπλοκότητα — Φεβρουάριος 2021¶
Μεταγραφή από το στιγμιότυπο IMG_5266.png.
IMG_5266.png¶
Ερώτηση 3 / 20 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός)
Πόσες μεταβάσεις υπάρχουν στο DFA που αναγνωρίζει το σύνολο των δυαδικών λέξεων που περιέχουν το πρότυπο 1001;
- [ ] 9
- [ ] 11
- [ ] 12
- [ ] 15
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-02¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 3¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: Το ελάχιστο DFA για «περιέχει 1001» έχει 5 καταστάσεις (επαληθεύθηκε με υπολογισμό κλάσεων ισοδυναμίας): \(q_0\) (τίποτα), \(q_1\) (τέλος «1»), \(q_2\) («10»), \(q_3\) («100»), \(q_4\) (βρέθηκε, τελική).
Μεταβάσεις: \(q_0\): 0→\(q_0\), 1→\(q_1\). \(q_1\): 0→\(q_2\), 1→\(q_1\). \(q_2\): 0→\(q_3\), 1→\(q_1\). \(q_3\): 0→\(q_0\), 1→\(q_4\). \(q_4\): 0,1→\(q_4\).
Ένα πλήρες DFA έχει \(5\cdot2=10\) μεταβάσεις, αριθμός που δεν υπάρχει στις επιλογές. Αν στο διάγραμμα η τελική κατάσταση σχεδιάζεται με ένα βέλος-βρόχο με ετικέτα «0,1» (μία ακμή αντί για δύο), προκύπτουν \(2+2+2+2+1=9\) βέλη.
Πιθανότερη απάντηση: 9 (με την παραπάνω σύμβαση σχεδίασης· χαμηλή βεβαιότητα).
Λύση 3 (τρίτη γνώμη): Σωστή επιλογή: - [x] 12
Αιτιολόγηση:
1. Το αλφάβητο των δυαδικών λέξεων είναι \(\Sigma = \{0, 1\}\), δηλαδή \(|\Sigma| = 2\).
2. Εξ ορισμού, σε ένα DFA (ντετερμινιστικό πεπερασμένο αυτόματο) η συνάρτηση μετάβασης είναι πλήρης: \(\delta: Q \times \Sigma \to Q\). Επομένως, από κάθε κατάσταση \(q \in Q\) εξέρχεται ακριβώς μία μετάβαση για κάθε σύμβολο του αλφαβήτου, άρα ο συνολικός αριθμός μεταβάσεων του DFA ισούται με \(|Q| \times |\Sigma| = 2|Q|\).
3. Ο συνολικός αριθμός μεταβάσεων ενός δυαδικού DFA είναι υποχρεωτικά άρτιος αριθμός. Μεταξύ των διαθέσιμων επιλογών (\(9, 11, 12, 15\)), ο μόνος άρτιος αριθμός είναι το 12 (αντιστοιχεί σε DFA με \(|Q| = 6\) καταστάσεις, \(6 \times 2 = 12\)).
4. Η επιλογή 12 επιβεβαιώνεται και από το στιγμιότυπο της ηλεκτρονικής εξέτασης (IMG_5266.png).
Η λύση Α επέλεξε το 9 υποθέτοντας αυθαίρετα ότι οι μεταβάσεις μετρούνται ως σχεδιαστικά βέλη όπου το διπλό loop «0,1» μετρά ως μία ακμή (\(2 \times 4 + 1 = 9\)), ενώ η λύση Β βασίστηκε στον αυστηρό μαθηματικό ορισμό του DFA όπου το πλήθος μεταβάσεων είναι \(2|Q|\) (υποχρεωτικά άρτιος, άρα μονοσήμαντα 12).