Θεωρία Υπολογισμού και Πολυπλοκότητα — Ιούνιος 2024¶
Μεταγραφή από τη φωτογραφία IMG_20240613_184352.jpg (σελίδα 2 από 8) και το στιγμιότυπο Screenshot_2024-06-12_153635.png.
IMG_20240613_184352.jpg¶
Το ελάχιστο πλήθος καταστάσεων DFA για τη γλώσσα που αναγνωρίζεται από την κανονική έκφραση \((00)^*(11)^*\) είναι ______.
Ερώτηση 7: Πόσα DFA με 2 καταστάσεις μπορούν να οριστούν στο αλφάβητο {0,1};
Ερώτηση 8: Έστω w λέξη μήκους n στο αλφάβητο {0,1}*. Έστω L το σύνολο όλων των υπολέξεων της w. Το ελάχιστο πλήθος καταστάσεων NFA που αναγνωρίζει τη L είναι ______.
Ερώτηση 9: Δίνεται πεπερασμένο αυτόματο M με n καταστάσεις. Σύμφωνα με τον αλγόριθμο που ελέγχει αν η L(M) είναι κενή, "τρέχουμε" το M για όλες τις λέξεις με μήκος μεταξύ ______ και ______.
Ερώτηση 10: Δίνεται το NFA αριστερά στο σχήμα. Ποιο είναι το ισοδύναμο DFA που προκύπτει με την εφαρμογή της κατασκευαστικής μεθόδου που βασίζεται στα σύνολα E(q) (ε-closure) για κάθε κατάσταση q του δοσμένου NFA;
[Σχήμα: NFA με 3 καταστάσεις A, B, C. Αρχική κατάσταση A με self-loop 0, 1. Μετάβαση από A σε B με 1. Μετάβαση από B σε C με 1. Μετάβαση από C σε B με 0. Τελική κατάσταση C.]
Ερώτηση 11: "Στο διάγραμμα καταστάσεων ενός NFA, αν κάνω τις τελικές καταστάσεις μη τελικές και τις μη τελικές τελικές προκύπτει NFA που αναγνωρίζει τη συμπληρωματική γλώσσα". - [ ] Αληθές - [ ] Ψευδές
Ερώτηση 12: Αν A είναι κανονική γλώσσα, τότε η γλώσσα \(A^R\) είναι: (\(L^R\): η αντίστροφη της γλώσσας L) - [ ] πάντα κανονική γλώσσα - [ ] πάντα μη κανονική - [ ] μπορεί να είναι είτε κανονική είτε μη κανονική γλώσσα - [ ] εξαρτάται από τη γλώσσα A
Ερώτηση 13: Δίνεται η γλώσσα \(T = \{x w x^R \mid x, w \in (0 \cup 1)^* - \{\varepsilon\}\}\). Είναι η Τ κανονική; (\(s^R\): η αντίστροφη λέξη της s) - [ ] Αν ναι, δώστε κανονική έκφραση _______________ - [ ] Αν όχι, δώστε λέξη για την εφαρμογή του Pumping Lemma (καλούμε p τη σταθερά) \(w =\) _______________ και πλήθος επαναλήψεων \(i =\) _______________ του μεσαίου τμήματος που οδηγεί στην παραγωγή λέξης που δεν ανήκει στη δοσμένη γλώσσα.
Σελίδα 2 από 8
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Screenshot_2024-06-12_153635.png¶
Ερώτηση 20:
Δίνεται πεπερασμένο αυτόματο Μ με k καταστάσεις. Για να αποφασίσουμε ότι η L(M) είναι πεπερασμένη αρκεί να βεβαιωθούμε ότι απορρίπτονται όλες οι λέξεις με μήκος μεταξύ k και ______
- [ ] 2k-1
- [ ] 3k-1
- [ ] 2k-3
- [ ] \(k^2-1\)
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2024-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Ερώτηση (μη αριθμημένη, πριν την 7): ελάχιστο DFA για \((00)^*(11)^*\)¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Κλάσεις ισοδυναμίας: \(q_0\) (αρχική/άρτιο πλήθος 0, τελική), \(A\) (περιττό πλήθος 0), \(B\) (μετά από περιττό πλήθος 1), \(E\) (μετά από άρτιο ≥2 πλήθος 1, τελική), και η κατάσταση-παγίδα. Μεταβάσεις: \(q_0\):0→\(A\), 1→\(B\)· \(A\):0→\(q_0\), 1→παγίδα· \(B\):1→\(E\), 0→παγίδα· \(E\):1→\(B\), 0→παγίδα. Επαληθεύτηκε με υπολογισμό: 5 καταστάσεις.
Ερώτηση 7¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Εκφώνηση¶
«Ερώτηση 7: Πόσα DFA με 2 καταστάσεις μπορούν να οριστούν στο αλφάβητο {0,1};»
Ανάλυση & Υπολογισμός¶
Ένα Ντετερμινιστικό Πεπερασμένο Αυτόματο (DFA) ορίζεται τυπικά ως μια 5-άδα \(M = (Q, \Sigma, \delta, q_0, F)\), όπου: - \(Q\) είναι το σύνολο καταστάσεων με \(|Q| = n = 2\) (έστω \(Q = \{q_0, q_1\}\)). - \(\Sigma = \{0, 1\}\) είναι το αλφάβητο εισόδου με \(|\Sigma| = m = 2\). - \(\delta: Q \times \Sigma \to Q\) είναι η συνάρτηση μετάβασης. Για κάθε ζεύγος \((q, \sigma) \in Q \times \Sigma\), υπάρχουν \(|Q| = 2\) πιθανές καταστάσεις προορισμού. Επειδή το πεδίο ορισμού έχει μέγεθος \(|Q| \cdot |\Sigma| = 2 \cdot 2 = 4\), το σύνολο όλων των πιθανών συναρτήσεων μετάβασης είναι: $\(|Q|^{|Q| \cdot |\Sigma|} = 2^{2 \cdot 2} = 2^4 = 16\)$ - \(q_0 \in Q\) είναι η αρχική κατάσταση. Υπάρχουν \(|Q| = 2\) επιλογές για την αρχική κατάσταση (αν θεωρηθεί σταθερή/χωρίς απώλεια γενικότητας, τότε 1 επιλογή). - \(F \subseteq Q\) είναι το σύνολο των τελικών καταστάσεων. Υπάρχουν \(2^{|Q|} = 2^2 = 4\) πιθανά υποσύνολα (\(\emptyset, \{q_0\}, \{q_1\}, \{q_0, q_1\}\)).
Ανάλογα με τη σύμβαση ορισμού διακριτών αυτομάτων σε δεδομένο σύνολο καταστάσεων: 1. Πλήρης τυπικός ορισμός (όπου επιλέγεται και η αρχική κατάσταση): $\(\text{Πλήθος DFA} = |Q|^{|Q| \cdot |\Sigma|} \cdot |Q| \cdot 2^{|Q|} = 16 \cdot 2 \cdot 4 = 128\)$ 2. Σύμβαση σταθερής αρχικής κατάστασης (π.χ. πάντα \(q_0\)): $\(\text{Πλήθος DFA} = |Q|^{|Q| \cdot |\Sigma|} \cdot 2^{|Q|} = 16 \cdot 4 = 64\)$ 3. Αν μετρώνται μόνο οι διακριτές συναρτήσεις μετάβασης (χωρίς τελικές καταστάσεις): $\(2^4 = 16\)$
Η τυπική θεωρητική απάντηση σε επίπεδο τυπικών 5-άδων είναι 128 (ή 64 αν η αρχική κατάσταση θεωρείται δεδομένη).
Ερώτηση 8¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Για \(w=w_1\dots w_n\) NFA με καταστάσεις \(0,\dots,n\), όλες τελικές, αρχική την \(0\), μεταβάσεις \(i-1\xrightarrow{w_i}i\) και ε-μεταβάσεις \(0\to i\) για κάθε \(i\). Δέχεται ακριβώς τις υπολέξεις της \(w\) (κάθε υπολέξη \(w_{i+1..j}\) προκύπτει με ε-άλμα στην \(i\) και ανάγνωση έως την \(j\)). Κάτω φράγμα: για \(w=0^n\) η \(L=\{0^0,\dots,0^n\}\) απαιτεί \(n+1\) καταστάσεις. Απάντηση: \(n+1\). (Η απάντηση \(n+1\) ως γενικό ελάχιστο υποθέτει ότι επιτρέπονται ε-μεταβάσεις.)
Ερώτηση 9¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Αν η \(L(M)\) δεν είναι κενή, δέχεται λέξη με μήκος \(\le n-1\) (συντομότερη διαδρομή χωρίς επανάληψη κατάστασης). Τρέχουμε όλες τις λέξεις με μήκος από \(0\) έως \(n-1\).
Ερώτηση 10¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Το NFA δεν έχει ε-μεταβάσεις, άρα \(E(q)=\{q\}\). Κατασκευή υποσυνόλων από το \(\{A\}\) (με δεδομένα \(\delta(A,0)=\{A\}\), \(\delta(A,1)=\{A,B\}\), \(\delta(B,1)=\{C\}\), \(\delta(C,0)=\{B\}\)):
| κατάσταση | 0 | 1 |
|---|---|---|
| \(\{A\}\) (αρχική) | \(\{A\}\) | \(\{A,B\}\) |
| \(\{A,B\}\) | \(\{A\}\) | \(\{A,B,C\}\) |
| \(\{A,B,C\}\) (τελική, περιέχει την \(C\)) | \(\{A,B\}\) | \(\{A,B,C\}\) |
(Επαληθεύτηκε με πρόγραμμα.) DFA με 3 καταστάσεις.
Ερώτηση 11¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Ψευδές. Η εναλλαγή τελικών/μη τελικών συμπληρώνει τη γλώσσα μόνο σε DFA· σε NFA μια λέξη μπορεί να έχει και αποδεκτή και μη αποδεκτή διαδρομή, οπότε θα γινόταν δεκτή και πριν και μετά. Π.χ. NFA με δύο αρχικές επιλογές, μία αποδεκτή και μία μη.
Ερώτηση 12¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
«πάντα κανονική γλώσσα» (αντιστροφή των βελών του NFA, με ανταλλαγή αρχικής και τελικών καταστάσεων).
Ερώτηση 13¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Η \(T\) είναι κανονική: μια λέξη ανήκει στην \(T\) ανν έχει μήκος \(\ge3\) και αρχίζει και τελειώνει με το ίδιο σύμβολο (\(x=c\) μονοψήφιο και \(w\) το υπόλοιπο· αντίστροφα, κάθε \(x w x^R\) αρχίζει με το πρώτο γράμμα του \(x\) και τελειώνει με το ίδιο). Κανονική έκφραση:
Επαληθεύτηκε με εξαντλητικό έλεγχο έως μήκος 11.
Ερώτηση 20¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Η \(L(M)\) είναι άπειρη ανν δέχεται λέξη με μήκος στο \([k,2k-1]\) (λήμμα άντλησης: λέξη μήκους \(\ge k\) έχει κύκλο· συντομεύοντας τον κύκλο προκύπτει δεκτή λέξη μήκους \(<2k\) αν η αρχική ήταν \(\ge k\)· αντίστροφα μια τέτοια λέξη δίνει άπειρες με άντληση). Άρα η \(L(M)\) είναι πεπερασμένη αν απορρίπτονται όλες οι λέξεις με μήκος από \(k\) έως \(2k-1\).