Θεωρία Υπολογισμού και Πολυπλοκότητα — Σεπτέμβριος 2020 (επαναληπτική)¶
Μεταγραφή από το στιγμιότυπο Screenshot_63.png, όπου φαίνεται η επαναληπτική εξέταση Σεπτεμβρίου 2020.
Screenshot_63.png¶
Θεωρία Υπολογισμού (εξέταση Σεπτεμβρίου 2020) (Y301, NY301) Επαναληπτική εξέταση Σεπτεμβρίου 2020 για το μάθημα Θεωρία Υπολογισμού
Ερώτηση 12 / 20 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός)
Δίνεται πεπερασμένο αυτόματο Μ με k καταστάσεις. Για να αποφασίσουμε ότι η L(M) είναι κενή αρκεί να βεβαιωθούμε ότι απορρίπτονται όλες οι λέξεις με μήκος μεταξύ 0 και ______ .
- [ ] k-1
- [ ] 2k-1
- [ ] k
- [ ] k-2
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2020-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 12¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Αν ένα πεπερασμένο αυτόματο με \(k\) καταστάσεις δέχεται κάποια λέξη, δέχεται και μία λέξη μήκους \(\le k-1\): στη συντομότερη αποδεκτή διαδρομή καμία κατάσταση δεν επαναλαμβάνεται (αλλιώς θα κόβαμε τον κύκλο), άρα έχει το πολύ \(k\) καταστάσεις, δηλαδή \(\le k-1\) μεταβάσεις. Άρα αρκεί να ελέγξουμε ότι απορρίπτονται όλες οι λέξεις με μήκος από \(0\) έως \(k-1\).
Απάντηση: \(k-1\).