Θεωρία Υπολογισμού και Πολυπλοκότητα — Φεβρουάριος 2023¶
Μεταγραφή από τα στιγμιότυπα -_-Google-_Opera_2_8_2023_7_00_42_PM_2.png και image.png.
-_-Google-_Opera_2_8_2023_7_00_42_PM_2.png¶
[Λείπει από τη φωτογραφία: η αρχή της ερώτησης]
του S που γίνονται αποδεκτές από το M είναι;
Δίνεται πεπερασμένο αυτόματο Μ με k καταστάσεις. Για να αποφασίσουμε ότι η L(M) είναι πεπερασμένη αρκεί να βεβαιωθούμε ότι απορρίπτονται όλες οι λέξεις με μήκος μεταξύ k και ______ .
- [ ] 2k-1
- [ ] 3k-1
- [ ] 2k-3
- [ ] \(k^2-1\)
image.png¶
Ερώτηση 19 / 20 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός)
Συμπληρώστε χρησιμοποιώντας τη σταθερά p, που συμβολίζει το μέγιστο μήκος λέξης στη γλώσσα L. Πρόταση: Οι πεπερασμένες γλώσσες ικανοποιούν τετριμμένα το Pumping Lemma για μήκος λέξης \(n =\) _____
- [ ] p
- [ ] p+1
- [ ] p-1
- [ ] Τίποτα από τα παραπάνω
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2023-02.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):dfa.png
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: φωτογραφία απάντησης φοιτητή (dfa.png, χωρίς ένδειξη συνεδρίας· στο Discord αναρτήθηκε 2026-06-21)
Προσοχή
Η ερώτηση της dfa.png («Ερώτηση 6 / 20», DFA για δυαδικές λέξεις μήκους τουλάχιστον 3 με 3ο σύμβολο 1) δεν εμφανίζεται στη μεταγραφή της συνεδρίας 2023-02. Η συσχέτιση με τη συνεδρία δεν έχει επιβεβαιωθεί· στο Discord η φωτογραφία αναρτήθηκε στις 2026-06-21. Η απάντηση των 5 καταστάσεων είναι συνεπής με το ελάχιστο πλήρες DFA (αρχική, καταστάσεις για 1 και 2 σύμβολα, αποδοχής και παγίδα). Το 4 προκύπτει αν η συνάρτηση μετάβασης είναι μερική, όπως σημειώνει η απάντηση.
Λύσεις — Θεωρία Υπολογισμού και Πολυπλοκότητας — Φεβρουάριος 2023¶
Απάντηση φοιτητή στη φωτογραφία dfa.png. Η συνεδρία στην οποία ανήκει η ερώτηση δεν έχει επιβεβαιωθεί.
dfa.png¶
Ερώτηση 31:
Ερώτηση 6 / 20 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός)
Ποιο είναι το ελάχιστο πλήθος καταστάσεων DFA για τη γλώσσα που περιέχει δυαδικές λέξεις με μήκος τουλάχιστον 3 που έχουν ως 3ο σύμβολο το 1;
- [ ] 3
- [ ] 4
- [ ] 5
- [ ] 1
Απάντηση: 5 καταστάσεις, εξηγείται και παρακάτω (4 καταστάσεις, με partial function αφαιρείς το reject state.)
[Σχήμα: Χειρόγραφο διάγραμμα DFA με 5 καταστάσεις: αρχική κατάσταση -> με 0,1 στη 2η -> με 0,1 στην 3η -> με 1 στην 4η (τελική κατάσταση με self-loop 0,1) και με 0 από την 3η στην 5η κατάσταση-παγίδα (reject state σημειωμένη με Χ).]