Θεωρία Υπολογισμού και Πολυπλοκότητα — Ιούνιος 2026¶
Μεταγραφή από τις φωτογραφίες 1000002308.jpg (σελίδα 1 από 10) και 1000002306.jpg (σελίδα 2 από 10), και τα στιγμιότυπα Screenshot_2026-06-22_195122.png, Screenshot_2026-06-22_195253.png και Screenshot_2026-06-22_195210.png, με τη σειρά των ερωτήσεων.
1000002308.jpg¶
Διάρκεια εξέτασης: 2 ώρες Βαθμολόγηση: οι μονάδες για κάθε ερώτηση/υποερώτηση υπάρχουν δίπλα τους - προσμετρώνται μόνον οι [ορθές απαντήσεις (δεν υπάρχει "αρνητική βαθμολογία")] [Κατανομή απαντήσεων: Μη ευκρινείς απαντήσεις δεν θα ληφθούν υπόψιν.]
ΕΡΩΤΗΣΗ 1 [1 ΜΟΝΑΔΑ] [Δώστε κανονικές εκφράσεις με το ζητούμενο πλήθος συμβόλων για τις παρακάτω γλώσσες.]
| Γλώσσα | Κανονική έκφραση |
|---|---|
| \(L_1 = \{w \in \{0,1\}^* \mid w \text{ δεν περιέχει δύο συνεχόμενα 1}\}\) – 12 σύμβολα | |
| \(L_2 = \{w \in \{a,b\}^* \mid w \text{ περιέχει ακριβώς μία εμφάνιση της aaa}\}\) – 29 σύμβολα | |
| \(L_3 = \{w \in \{0,1\}^* \mid w \text{ δεν περιέχει την 110}\}\) – 9 σύμβολα | |
| \(L_4 =\) Όλες οι λέξεις της \(a^*b^*\) με μήκος πολλαπλάσιο του 3 (π.χ., η γλώσσα περιέχει τη λέξη aaaabb αλλά δεν περιέχει τις λέξεις ababab, aaabb) – 23 σύμβολα |
ΕΡΩΤΗΣΗ 2 [2 ΜΟΝΑΔΕΣ] Σχεδιάστε DFA με 6 καταστάσεις για τη γλώσσα L που περιλαμβάνει τις λέξεις του \(\{a,b\}^*\) που περιέχουν την υπολέξη bba ή την υπολέξη aaa, π.χ., \(bbaab \in L, babab \notin L\).
Σελίδα 1 από 10
1000002306.jpg¶
[1] Σχεδιάστε DFA με 4 καταστάσεις για τη γλώσσα \(L = \{w \in \{0,1\}^* : w \text{ ξεκινάει με 0 και έχει περιττό μήκος ή ξεκινάει με 1 και έχει άρτιο μήκος}\}\).
ΕΡΩΤΗΣΗ 3 [2 ΜΟΝΑΔΕΣ] Ποιο είναι το ελάχιστο πλήθος καταστάσεων σε DFA που αναγνωρίζει τη γλώσσα:
| Γλώσσα | Ελάχιστο πλήθος καταστάσεων |
|---|---|
| [2/5] \(\{a^n b^{2n} \mid [δυσανάγνωστο: n,m] \ge 0\}\) | |
| [2/5] \(\{w \in \{a,b\}^* \mid \eta\ w\ \text{περιέχει τις ab και ba ίσο πλήθος φορών}\}\) | |
| [2/5] \(\{w \in \{0,1\}^* \mid \eta\ w\ \text{περιέχει τουλάχιστον ένα 1 και άρτιος αριθμός 0 ακολουθεί το τελευταίο 1}\}\) | |
| [2/5] \(\{a^{nk} \mid k>0, \text{n θετική ακέραια σταθερά}\}\) | |
| [2/5] δυαδικές λέξεις στις οποίες τα δύο τελευταία σύμβολα είναι ίδια |
ΕΡΩΤΗΣΗ 4 [1 ΜΟΝΑΔΑ] [1/2] Δίνονται: \(A = \{1^k y \mid k \ge 1, y \in \{0,1\}^* \text{ και η y περιέχει τουλάχιστον } k \text{ "1"}\}\) \(B = \{1^k y \mid k \ge 1, y \in \{0,1\}^* \text{ και η y περιέχει το πολύ } (B)\ k \text{ "1"}\}\) Τι ισχύει; - [ ] Μόνο η Α είναι κανονική - [ ] Μόνο η Β είναι κανονική - [ ] Και η Α και η Β είναι κανονικές γλώσσες - [ ] Ούτε η Α ούτε η Β είναι κανονική γλώσσα
[1/2] Δίνεται η γλώσσα \(T = \{x w x^R \mid x, w \in \{0 \cup 1\}^* - \{\varepsilon\}\}\). Είναι η Τ κανονική; (\(x^R\): η αντίστροφη λέξη της x) Αν ναι, δώστε κανονική έκφραση: _______________ Αν όχι, δώστε λέξη για την εφαρμογή του Pumping Lemma (καλούμε p τη σταθερά) \(w =\) _______________ και πλήθος επαναλήψεων \(i =\) _______________ του μεσαίου τμήματος που οδηγεί στην παραγωγή λέξης που δεν ανήκει στη δοσμένη γλώσσα.
ΕΡΩΤΗΣΗ 5 [1 ΜΟΝΑΔΑ] [1] Μετατρέψτε το NFA του σχήματος σε ισοδύναμο DFA χρησιμοποιώντας την κατασκευαστική μέθοδο που βασίζεται στη δημιουργία υποσυνόλων (subset construction).
[Σχήμα: NFA με 3 καταστάσεις A, B, C. Αρχική κατάσταση A με self-loop 0, 1. Μετάβαση από A σε B με 1. Μετάβαση από B σε C με 1. Μετάβαση από C σε B με 0. Τελική κατάσταση C.]
Σελίδα 2 από 10
Screenshot_2026-06-22_195122.png¶
CEID_24Y301, ΧΡ. ΚΑΚΛΑΜΑΝΗΣ, Ε. ΠΑΠΑΪΩΑΝΝΟΥ
ΕΡΩΤΗΣΗ 9 [1 ΜΟΝΑΔΑ] [1] Δώστε διάγραμμα καταστάσεων με 7 καταστάσεις για μη ντετερμινιστικό αυτόματο στοίβας (nPDA) για τη γλώσσα που είναι ορισμένη στο αλφάβητο {a,b} και περιέχει λέξεις της μορφής \(a^{2n} b^{3n}, n \ge 0\).
ΕΡΩΤΗΣΗ 10 [1 ΜΟΝΑΔΑ] [1] Δώστε διάγραμμα καταστάσεων με 6 καταστάσεις για μηχανή Turing που να κάνει τα εξής με είσοδο #w, όπου \(w \in \{0,1\}^*\). Έστω \(n = |w|\). Αν n άρτιος, τότε η Μ μετατρέπει την είσοδο #w σε \(\#0^n\). Αν n περιττός, τότε η Μ μετατρέπει την είσοδο #w σε \(\#1^n\). Υποθέστε ότι η κενή λέξη \(\varepsilon\) είναι λέξη με άρτιο μήκος.
ΕΡΩΤΗΣΗ 11 [2 ΜΟΝΑΔΕΣ] Συμπληρώστε.
Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.
| Πρόταση | Σωστό (Σ) / Λάθος (Λ) |
|---|---|
| [1/5] [δυσανάγνωστο... \(1^3, a \le 2^k\)]. Η L δεν είναι κανονική γλώσσα. | |
| [1/5] Αν L είναι κάποια γλώσσα, τότε το σύνολο \(L^*\) είναι άπειρο. | |
| [1/5] Έστω γλώσσα L είναι μοναδιαία (unary) γλώσσα (π.χ. L γνήσιο υποσύνολο του \(1^*\)). Η L μπορεί να μην είναι κανονική. Αλλά η \(L^*\) είναι πάντα κανονική. | |
| [1/5] Αν υπάρχει NFA N με n καταστάσεις και σταθερό αριθμό συμβόλων εισόδου, τότε υπάρχει ισοδύναμη κανονική έκφραση R για το N - που προκύπτει μέσω της κατασκευαστικής μεθόδου με χρήση GNFA - με μήκος \(O(n)\). | |
| [1/5] Για κάθε γλώσσα L, \(\{www \in L\}\) ισούται με LLL. | |
| [1/5] Έστω \(N_1, N_2\) δύο NFA με \(n_1\) και \(n_2\) καταστάσεις, αντίστοιχα. Τότε υπάρχει DFA με το πολύ \(n_1 \times n_2\) καταστάσεις που αναγνωρίζει τη γλώσσα \(L(N_1) \cap L(N_2)\). | |
| [1/5] Έστω P ένα πρόγραμμα σε C++ και η αναπαράστασή του. Έστω \(L = \{<P> : P \text{ πρόγραμμα C++ που γίνεται compile χωρίς λάθη (errors)}\}\). Υποθέστε ότι ο C++ compiler χρησιμοποιεί κάποια CFG για parsing. Η L είναι μη διαγνώσιμη (undecidable). |
|
| [1/5] Η γλώσσα που παράγεται από κάθε γραμματική χωρίς συμφραζόμενα (CFG) που όλοι οι κανόνες της είναι της μορφής \(A \to wB\) ή \(A \to \varepsilon\), όπου A,B είναι μεταβλητές και w είναι μια μη κενή λέξη, είναι κανονική. | |
| [1/5] Το συμπλήρωμα μιας γλώσσας χωρίς συμφραζόμενα (CFL) είναι διαγνώσιμη (decidable) γλώσσα. | |
| [1/5] Το σύνολο των decidable γλωσσών είναι μη αριθμήσιμο (uncountable). |
Screenshot_2026-06-22_195253.png¶
CEID_24Y301, ΧΡ. ΚΑΚΛΑΜΑΝΗΣ, Ε. ΠΑΠΑΪΩΑΝΝΟΥ
ΕΡΩΤΗΣΗ 12 [3 ΜΟΝΑΔΕΣ] Σχεδιάστε τα gadgets που χρησιμοποιούνται για την απόδειξη NP-πληρότητας για τα προβλήματα CLIQUE, VERTEX COVER και IS όταν γίνεται αναγωγή από το πρόβλημα 3SAT για το στιγμιότυπο \((x_1 \lor \bar{x}_2 \lor x_3) \quad (\bar{x}_1 \lor \bar{x}_2 \lor x_3) \quad (\bar{x}_1 \lor \bar{x}_2 \lor \bar{x}_3)\) και για \((x_1, x_2, x_3)=(1, 0, 1)\) υποδείξτε στο σχήμα σας την αντίστοιχη δομή.
| Πρόβλημα | Περιγραφή |
|---|---|
| [1] CLIQUE | \(\{<G, k> \mid G \text{ μη κατευθυνόμενο γράφημα με k-κλίκα (clique)}\}\) |
| [1] VERTEX-COVER | \(\{<G, k> \mid G \text{ μη κατευθυνόμενο γράφημα με κάλυψη κορυφών μεγέθους k (k-node vertex cover)}\}\) |
| [1] INDEPENDENT SET | ${ |
ΕΡΩΤΗΣΗ 13 [2 ΜΟΝΑΔΕΣ] Επιλέξτε τη σωστή απάντηση σημειώνοντας Χ στο κουτάκι αριστερά της:
[1/4] Ποια από τα παρακάτω προβλήματα είναι μη διαγνώσιμα (undecidable); I. Δεδομένων NFA \(N_1\) και \(N_2\), είναι \(L(N_1) \cap L(N_2) = \varnothing\); II. Δεδομένων CFG \(G = (V,\Sigma,R,S)\) και λέξης \(x \in \Sigma^*\), ισχύει \(x \in L(G)\); III. Δεδομένων CFG \(G_1\) και \(G_2\), ισχύει \(L(G_1) = L(G_2)\); IV. Δεδομένης μηχανής Turing M, ισχύει \(L(M) = \varnothing\); - [ ] I και IV - [ ] II και III - [ ] III και IV - [ ] II και IV
[1/4] Για \(\Sigma=\{a,b\}\), ποιο από τα παρακάτω σύνολα είναι μη μετρήσιμο (not countable); - [ ] Το σύνολο όλων των λέξεων του \(\Sigma\) - [ ] Το σύνολο όλων των κανονικών γλωσσών που ορίζονται στο \(\Sigma\) - [ ] Το σύνολο όλων των γλωσσών που ορίζονται στο \(\Sigma\) - [ ] Το σύνολο όλων των γλωσσών που ορίζονται στο \(\Sigma\) και γίνονται δεκτές (accepted) κάποια μηχανή Turing
Screenshot_2026-06-22_195210.png¶
CEID_24Y301, ΧΡ. ΚΑΚΛΑΜΑΝΗΣ, Ε. ΠΑΠΑΪΩΑΝΝΟΥ
[1/4] Έστω 3 προβλήματα απόφασης \(P_1, P_2\) και \(P_3\). Το \(P_1\) είναι διαγνώσιμο (decidable) και το \(P_2\) είναι μη διαγνώσιμο (undecidable). Ποια από τις παρακάτω προτάσεις είναι αληθής; - [ ] Το \(P_3\) είναι decidable αν υπάρχει αναγωγή από το \(P_1\) στο \(P_3\) - [ ] Το \(P_3\) είναι undecidable αν υπάρχει αναγωγή από το \(P_3\) στο \(P_2\) - [ ] Το \(P_3\) είναι undecidable αν υπάρχει αναγωγή από το \(P_2\) στο \(P_3\) - [ ] Το \(P_3\) είναι decidable αν υπάρχει αναγωγή από το \(P_3\) στο συμπλήρωμα του \(P_2\)
[1/4] \(L_1\) διαγνώσιμη (decidable/recursive) γλώσσα, \(L_2\) και \(L_3\) γλώσσες που είναι αναγνωρίσιμες (recognizable/recursively enumerable) αλλά όχι διαγνώσιμες (not recursive). Ποια από τις προτάσεις δεν είναι απαραίτητα αληθής; - [ ] \(L_2 - L_1\) είναι αναγνωρίσιμη (recursively enumerable) - [ ] \(L_1 - L_3\) είναι αναγνωρίσιμη (recursively enumerable) - [ ] \(L_2 \cap L_1\) είναι αναγνωρίσιμη (recursively enumerable) - [ ] \(L_2 \cup L_1\) είναι αναγνωρίσιμη (recursively enumerable)
[1/4] Συμβολίζουμε με \(A \le_m B\) το ότι υπάρχει απεικονιστική αναγωγή (mapping reduction) από τη γλώσσα A στη γλώσσα B. Ποια από τις προτάσεις είναι ψευδής; - [ ] Αν \(A \le_m B\) και B είναι διαγνώσιμη (recursive) τότε A διαγνώσιμη (recursive) - [ ] Αν \(A \le_m B\) και A είναι διαγνώσιμη (undecidable) τότε B μη διαγνώσιμη (undecidable) [sic: «είναι διαγνώσιμη (undecidable)» όπως τυπώνεται] - [ ] Αν \(A \le_m B\) και B είναι αναγνωρίσιμη (recursively enumerable) τότε A αναγνωρίσιμη (recursively enumerable) - [ ] Αν \(A \le_m B\) και B είναι μη αναγνωρίσιμη (not recursively enumerable) τότε A μη αναγνωρίσιμη (not recursively enumerable)
[1/4] Για \(s \in \{0 \cup 1\}^*\) συμβολίζουμε με d(s) τη δεκαδική τιμή του s (π.χ. d(101) = 5). Έστω \(L = \{s \in \{0 \cup 1\}^* \mid d(s) \bmod 5 = 2 \text{ και } d(s) \bmod 7 \ne 4\}\). Ποια από τις προτάσεις είναι αληθής; - [ ] Η L είναι αναδρομικά αριθμήσιμη (recursively enumerable) αλλά όχι αναδρομική (recursive) - [ ] Η L είναι αναδρομική (recursive) αλλά όχι γλώσσα χωρίς συμφραζόμενα - [ ] Η L είναι γλώσσα χωρίς συμφραζόμενα αλλά όχι κανονική - [ ] Η L είναι κανονική
[1/4] Έστω X αναδρομική (recursive) γλώσσα και Y αναδρομικά αριθμήσιμη (recursively enumerable) αλλά όχι αναδρομική (recursive) γλώσσα. W και Z είναι γλώσσες τέτοιες ώστε να υπάρχει αναγωγή από την Y' στη W και από τη Z στη X'. Ποια από τις προτάσεις είναι αληθής; (X', Y': συμπληρωματικές γλώσσες των X και Y, αντίστοιχα) - [ ] W μπορεί να είναι αναδρομικά αριθμήσιμη (recursively enumerable) και Z είναι αναδρομική (recursive) - [ ] W μπορεί να είναι αναδρομική (recursive) και Z είναι αναδρομικά αριθμήσιμη (recursively enumerable) - [ ] W όχι αναδρομικά αριθμήσιμη (recursively enumerable) και Z αναδρομική (recursive) - [ ] W όχι αναδρομικά αριθμήσιμη (recursively enumerable) και Z όχι αναδρομική (recursive)
[1/4] Δεν είναι γνωστό αν P = NP. Έστω γλώσσα L που ορίζεται ως εξής: \(L = \{0 \cup 1\}^* \text{ αν } P = NP, \text{ και } \{\} \text{ διαφορετικά}\). Ποια από τις προτάσεις είναι αληθής; - [ ] L είναι αναδρομική (recursive) - [ ] L είναι αναδρομικά αριθμήσιμη (recursively enumerable) αλλά όχι αναδρομική (recursive) - [ ] L δεν είναι αναδρομικά αριθμήσιμη (recursively enumerable) - [ ] Το αν η L είναι αναδρομική (recursive) ή όχι θα μπορεί να απαντηθεί αφού διαπιστωθεί αν P = NP
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2026-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Ερώτηση 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
- \(L_1\) (χωρίς δύο διαδοχικά 1), 12 σύμβολα: \((0\cup10)^*(\varepsilon\cup1)\)
- \(L_2\) (ακριβώς μία εμφάνιση της \(aaa\)), 29 σύμβολα: \((\varepsilon\cup b\cup ab\cup aab)^*\,aaa\,(\varepsilon\cup b\cup ba\cup baa)^*\). Αιτιολόγηση: πριν την \(aaa\) η λέξη δεν τελειώνει σε \(a\) και δεν έχει \(aaa\) (τμήματα \(b,ab,aab\))· μετά, δεν αρχίζει με \(a\) και δεν έχει \(aaa\). (Χωρίς τα δύο περιττά «ε∪» η έκφραση έχει 25 σύμβολα και είναι ισοδύναμη.)
- \(L_3\) (χωρίς 110), 9 σύμβολα: \((0\cup10)^*1^*\). Μετά από το πρώτο \(11\) όλα τα επόμενα σύμβολα είναι 1.
- \(L_4\) (λέξεις της \(a^*b^*\) με μήκος πολλαπλάσιο του 3), 23 σύμβολα: \((aaa)^*(\varepsilon\cup abb\cup aab)(bbb)^*\). Τα υπόλοιπα των πλήθους \(a\) και \(b\) mod 3 είναι \((0,0),(1,2),(2,1)\).
Ερώτηση 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
DFA με 6 καταστάσεις: \(S\) (αρχική, τίποτα), \(A_1\) (τελευταίο γράμμα \(a\) μετά από όχι-\(a\)), \(A_2\) (τελευταία \(aa\)), \(B_1\) (τελευταίο \(b\) μετά από όχι-\(b\)), \(B_2\) (τελευταία \(bb\)), \(F\) (τελική, βρέθηκε \(aaa\) ή \(bba\), παγιδευτική).
| \(a\) | \(b\) | |
|---|---|---|
| \(S\) | \(A_1\) | \(B_1\) |
| \(A_1\) | \(A_2\) | \(B_1\) |
| \(A_2\) | \(F\) | \(B_1\) |
| \(B_1\) | \(A_1\) | \(B_2\) |
| \(B_2\) | \(F\) | \(B_2\) |
| \(F\) | \(F\) | \(F\) |
Επαληθεύτηκε ότι είναι το ελάχιστο DFA (6 κλάσεις).
Μη αριθμημένο μπλοκ: DFA με 4 καταστάσεις για «ξεκινά με 0 και περιττό μήκος, ή ξεκινά με 1 και άρτιο μήκος»¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη
Το ελάχιστο DFA έχει 3 καταστάσεις: \(s\) (αρχική, μη τελική), \(A\) (τελική), \(B\) (μη τελική), με \(s\xrightarrow0A\), \(s\xrightarrow1B\), \(A\xrightarrow{0,1}B\), \(B\xrightarrow{0,1}A\). (Μετά από 0 με περιττό μήκος, ή μετά από 1 με άρτιο μήκος, είμαστε στην κατάσταση «αποδεκτό μήκος».) Για να έχει ακριβώς 4 καταστάσεις, διπλασιάζουμε μια ισοδύναμη κατάσταση: \(s\xrightarrow1B'\), \(B'\xrightarrow{0,1}A\), και \(A\xrightarrow{0,1}B\), \(B\xrightarrow{0,1}A\). Το αυτόματο είναι έγκυρο αλλά όχι ελάχιστο.
Ερώτηση 3¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στην εικόνα 1000002306.jpg (σελίδα 2 από 10) διακρίνονται ευκρινώς και οι 5 γραμμές του πίνακα της Ερώτησης 3:
Στην 1η γραμμή, η γλώσσα αναγράφεται καθαρά ως:
$\(\{a^n b^{2m} \mid n, m \ge 0\}\)$
(δηλαδή οι εκθέτες των \(a\) και \(b\) είναι ανεξάρτητοι ακέραιοι \(n \ge 0\) και \(m \ge 0\), και όχι \(2n\)).
Αναλυτικός υπολογισμός ελάχιστου πλήθους καταστάσεων DFA για κάθε γλώσσα:¶
- Γλώσσα \(\{a^n b^{2m} \mid n, m \ge 0\}\):
- Περιγράφεται από την κανονική έκφραση \(a^*(bb)^*\).
- Οι λέξεις αποτελούνται από αυθαίρετο πλήθος \(a\) ακολουθούμενο από άρτιο πλήθος \(b\).
- Καταστάσεις ελάχιστου DFA (4 καταστάσεις):
- \(q_0\) (αρχική, αποδοχής): έχει διαβάσει μόνο \(a\) (0 ή περισσότερα, \(0\) σύμβολα \(b\)). Με \(a \to q_0\), με \(b \to q_1\).
- \(q_1\) (απόρριψης): έχει διαβάσει περιττό πλήθος \(b\). Με \(b \to q_2\), με \(a \to q_{\text{trap}}\) (δεν επιτρέπεται \(a\) μετά από \(b\)).
- \(q_2\) (αποδοχής): έχει διαβάσει άρτιο πλήθος \(b \ge 2\). Με \(b \to q_1\), με \(a \to q_{\text{trap}}\).
- \(q_{\text{trap}}\) (παγίδα / νεκρή κατάσταση, απόρριψης): με \(a, b \to q_{\text{trap}}\).
-
Αποτέλεσμα: 4 καταστάσεις (ή 3 αν θεωρηθεί μη πλήρες DFA χωρίς ρητή κατάσταση παγίδας).
-
Γλώσσα \(\{w \in \{a,b\}^* \mid \eta\ w\ \text{περιέχει τις ab και ba ίσο πλήθος φορών}\}\):
- Κάθε εμφάνιση της \(ab\) αλλάζει το τρέχον σύμβολο από \(a\) σε \(b\), ενώ κάθε εμφάνιση της \(ba\) αλλάζει το σύμβολο από \(b\) σε \(a\).
- Επομένως, το πλήθος των \(ab\) ισούται με το πλήθος των \(ba\) αν και μόνο αν η λέξη είναι η κενή λέξη \(\varepsilon\), ή το πρώτο και το τελευταίο σύμβολο της λέξης ταυτίζονται: $\(L = \{\varepsilon\} \cup a(a+b)^*a \cup b(a+b)^*b \cup \{a, b\}\)$
- Καταστάσεις ελάχιστου DFA (5 καταστάσεις):
- \(q_0\) (αρχική, αποδοχής): κενή λέξη \(\varepsilon\). Με \(a \to q_a\), με \(b \to q_b\).
- \(q_a\) (αποδοχής): ξεκίνησε με \(a\) και τελευταίο σύμβολο \(a\). Με \(a \to q_a\), με \(b \to q_{ab}\).
- \(q_{ab}\) (απόρριψης): ξεκίνησε με \(a\) και τελευταίο σύμβολο \(b\). Με \(b \to q_{ab}\), με \(a \to q_a\).
- \(q_b\) (αποδοχής): ξεκίνησε με \(b\) και τελευταίο σύμβολο \(b\). Με \(b \to q_b\), με \(a \to q_{ba}\).
- \(q_{ba}\) (απόρριψης): ξεκίνησε με \(b\) και τελευταίο σύμβολο \(a\). Με \(a \to q_{ba}\), με \(b \to q_b\).
-
Αποτέλεσμα: 5 καταστάσεις.
-
Γλώσσα \(\{w \in \{0,1\}^* \mid \eta\ w\ \text{περιέχει τουλάχιστον ένα 1 και άρτιος αριθμός 0 ακολουθεί το τελευταίο 1}\}\):
- Καταστάσεις ελάχιστου DFA (3 καταστάσεις):
- \(q_0\) (αρχική, απόρριψης): δεν έχει εμφανιστεί ακόμα '1'. Με \(0 \to q_0\), με \(1 \to q_1\).
- \(q_1\) (αποδοχής): το τελευταίο σύμβολο ήταν '1', άρα ακολουθείται από 0 μηδενικά (άρτιος αριθμός). Με \(1 \to q_1\), με \(0 \to q_2\).
- \(q_2\) (απόρριψης): μετά το τελευταίο '1' ακολουθεί περιττός αριθμός μηδενικών. Με \(0 \to q_1\) (γίνονται άρτια), με \(1 \to q_1\) (νέο τελευταίο '1').
-
Αποτέλεσμα: 3 καταστάσεις.
-
Γλώσσα \(\{a^{nk} \mid k > 0, n \text{ θετική ακέραια σταθερά}\}\):
- Η γλώσσα είναι \((a^n)^+ = \{a^n, a^{2n}, a^{3n}, \dots\}\) στο μοναδιαίο αλφάβητο \(\{a\}\). Δεν περιέχει την κενή λέξη \(\varepsilon\) (\(k > 0\)).
- Το αυτόματο μετρά το μήκος modulo \(n\), αλλά πρέπει να διακρίνει το μήκος \(0\) (απόρριψη) από τα θετικά πολλαπλάσια του \(n\) (αποδοχή).
- Καταστάσεις ελάχιστου DFA (\(n+1\) καταστάσεις):
- \(q_0\) (αρχική, απόρριψης)
- \(q_1, q_2, \dots, q_{n-1}\) (απόρριψης)
- \(q_n\) (αποδοχής, αντιπροσωπεύει μήκος \(\equiv 0 \pmod n\) με \(k \ge 1\)) με μετάβαση με \(a \to q_1\).
-
Αποτέλεσμα: \(n + 1\) καταστάσεις (ή \(n\) καταστάσεις αν θεωρηθεί \(k \ge 0\)).
-
Γλώσσα δυαδικών λέξεων στις οποίες τα δύο τελευταία σύμβολα είναι ίδια:
- Κανονική έκφραση: \((0 + 1)^*(00 + 11)\).
- Καταστάσεις ελάχιστου DFA (5 καταστάσεις):
- \(q_\varepsilon\) (αρχική, απόρριψης, μήκος \(< 1\))
- \(q_0\) (απόρριψης, τελευταίο σύμβολο 0, προηγούμενο διάφορο ή κενό)
- \(q_1\) (απόρριψης, τελευταίο σύμβολο 1, προηγούμενο διάφορο ή κενό)
- \(q_{00}\) (αποδοχής, τα 2 τελευταία είναι 00)
- \(q_{11}\) (αποδοχής, τα 2 τελευταία είναι 11)
- Αποτέλεσμα: 5 καταστάσεις.
Ερώτηση 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Α: \(w\in A\iff w\) αρχίζει με 1 και περιέχει ≥2 «1» συνολικά (αρκεί \(k=1\)). Κανονική. Β: με \(L\) τα αρχικά 1 και \(T\) το συνολικό πλήθος: \(w\in B\iff L\ge1\wedge 2L\ge T\). Οι \(1^m0\) έχουν ανά δύο διαφορετικά «μέλλοντα» (\(1^m01^m\in B\), \(1^{m'}01^m\notin B\) για \(m'<m\)), άρα άπειρες κλάσεις: όχι κανονική.
Απάντηση: «Μόνο η Α είναι κανονική».
Δεύτερο ερώτημα: η \(T\) είναι κανονική, \(T=0(0\cup1)^+0\cup1(0\cup1)^+1\) (κάθε λέξη της \(T\) αρχίζει και τελειώνει με το ίδιο σύμβολο και έχει μήκος \(\ge3\), και αντίστροφα με \(x\) μονοψήφιο).
Ερώτηση 5¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Το NFA δεν έχει ε-μεταβάσεις. Κατασκευή υποσυνόλων:
| 0 | 1 | |
|---|---|---|
| \(\{A\}\) (αρχική) | \(\{A\}\) | \(\{A,B\}\) |
| \(\{A,B\}\) | \(\{A\}\) | \(\{A,B,C\}\) |
| \(\{A,B,C\}\) (τελική) | \(\{A,B\}\) | \(\{A,B,C\}\) |
Το DFA έχει 3 καταστάσεις και τελική την \(\{A,B,C\}\) (περιέχει την \(C\)).
Ερώτηση 9¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
nPDA για \(a^{2n}b^{3n}\) (στοίβα με πυθμένα \(\$\), σύμβολο \(X\)): - \(s_0\to s_1\): \(\varepsilon,\varepsilon\to\$\) - \(s_1\) βρόχος: \(a,\varepsilon\to X\) (ένα \(X\) για κάθε \(a\), δηλαδή \(2n\) \(X\)) - \(s_1\to s_2\): \(\varepsilon,\varepsilon\to\varepsilon\) - \(s_2\to s_3\): \(b,X\to\varepsilon\)· \(s_3\to s_4\): \(b,X\to\varepsilon\)· \(s_4\to s_2\): \(b,\varepsilon\to\varepsilon\) (τρία \(b\) αφαιρούν δύο \(X\)) - \(s_2\to s_5\): \(\varepsilon,\$\to\varepsilon\), και \(s_5\to s_6\): \(\varepsilon,\varepsilon\to\varepsilon\) (\(s_6\) τελική)
Συνολικά 7 καταστάσεις \(s_0,\dots,s_6\). Λειτουργεί γιατί τα \(2n\) \(X\) καταναλώνονται από \(n\) ομάδες των τριών \(b\). Επαληθεύτηκε με πρόγραμμα (με την \(s_5\) ως τελική· η \(s_6\) είναι απλώς μετάθεση της αποδοχής).
Ερώτηση 10¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Καταστάσεις: \(E\) (έχουμε διαβάσει άρτιο πλήθος συμβόλων του \(w\)), \(O\) (περιττό), \(L_0\) (επιστροφή, γράφουμε 0), \(L_1\) (επιστροφή, γράφουμε 1), \(q_{acc}\), \(q_{rej}\) (6 συνολικά, η \(q_{rej}\) δεν χρησιμοποιείται).
- \(E\): \(\#\to\#,R\) (παραμένει στην \(E\))· \(0/1\to x,R\) και πηγαίνει στην \(O\)· \(⌴\to⌴,L\) και πηγαίνει στην \(L_0\).
- \(O\): \(0/1\to x,R\) και πηγαίνει στην \(E\)· \(⌴\to⌴,L\) και πηγαίνει στην \(L_1\).
- \(L_0\): \(x\to0,L\)· \(\#\to\#\) και πηγαίνει στην \(q_{acc}\).
- \(L_1\): \(x\to1,L\)· \(\#\to\#\) και πηγαίνει στην \(q_{acc}\).
Επαληθεύτηκε με προσομοίωση για όλα τα \(w\) μήκους ≤8 (συμπεριλαμβανομένου του ε).
Ερώτηση 11¶
Αξιοπιστία: δεν λύθηκε
- Δεν λύθηκε: η πρόταση είναι δυσανάγνωστη.
- Λ. Αν \(L=\varnothing\) ή \(L=\{\varepsilon\}\) τότε \(L^*=\{\varepsilon\}\).
- Σ. Μια υπο-μονοειδής του \(\mathbb N\) είναι πεπερασμένα παραγόμενη και τελικά περιοδική, άρα η \(L^*\) είναι κανονική.
- Λ. Η μέθοδος GNFA μπορεί να δώσει εκθετικό μήκος· υπάρχουν NFA με \(n\) καταστάσεις που απαιτούν κανονική έκφραση μήκους \(2^{\Omega(n)}\) (σταθερό αλφάβητο).
- Λ (μέτρια): αν η πρόταση εννοεί \(\{www: w\in L\}\) (τρίπλασια επανάληψη της ίδιας λέξης), τότε δεν ισούται με \(LLL\) (π.χ. \(L=\{a,b\}\): το \(aab\in LLL\) αλλά δεν είναι της μορφής \(www\)).
- Λ. Η τομή δύο NFA με \(n_1,n_2\) καταστάσεις έχει NFA με \(n_1n_2\) καταστάσεις, αλλά το DFA μπορεί να χρειαστεί \(2^{n_1n_2}\).
- Λ (μέτρια): η πρόταση υπαινίσσεται ότι ο parser είναι CFG· ο έλεγχος σύνταξης είναι διαγνώσιμος. (Στην πράξη, οι templates της C++ είναι Turing-πλήρεις, αλλά η εκφώνηση δίνει την υπόθεση της CFG.)
- Σ. Γραμματική με κανόνες \(A\to wB\mid\varepsilon\) είναι δεξιά-γραμμική, άρα κανονική.
- Σ. Οι CFL είναι διαγνώσιμες (π.χ. με CYK), και το συμπλήρωμα διαγνώσιμης γλώσσας είναι διαγνώσιμο.
- Λ. Οι διαγνώσιμες γλώσσες αντιστοιχούν σε ΤΜ, και οι ΤΜ είναι αριθμήσιμες.
Ερώτηση 12¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Στιγμιότυπο: \(C_1=(x_1\vee\bar x_2\vee x_3)\), \(C_2=(\bar x_1\vee\bar x_2\vee x_3)\), \(C_3=(\bar x_1\vee\bar x_2\vee\bar x_3)\), ανάθεση \((1,0,1)\). Κάθε εμφάνιση λεξιγράμματος γίνεται κορυφή, 9 στο σύνολο: \(C_1\): \(x_1,\bar x_2,x_3\)· \(C_2\): \(\bar x_1,\bar x_2,x_3\)· \(C_3\): \(\bar x_1,\bar x_2,\bar x_3\). Με την ανάθεση, αληθή λεξιγράμματα: \(C_1\): και τα τρία· \(C_2\): \(\bar x_2,x_3\)· \(C_3\): \(\bar x_2\).
CLIQUE (k = 3 = πλήθος φράσεων): ακμές ανάμεσα σε κορυφές διαφορετικών φράσεων που δεν είναι συμπληρωματικές (\(x_i\) με \(\bar x_i\)). Κλίκα-πιστοποιητικό για \((1,0,1)\): επιλέγουμε από κάθε φράση ένα αληθές λεξίγραμμα, π.χ. \(x_1\) (από \(C_1\)), \(\bar x_2\) (από \(C_2\)), \(\bar x_2\) (από \(C_3\)). Είναι τριγωνική κλίκα, αφού τα \(x_1\)–\(\bar x_2\) και \(\bar x_2\)–\(\bar x_2\) δεν είναι συμπληρωματικά.
INDEPENDENT SET (k = 3): ίδιες κορυφές, με ακμές: (α) τρίγωνο μέσα σε κάθε φράση (9 ακμές), (β) ακμές ανάμεσα σε συμπληρωματικά λεξιγράμματα σε διαφορετικές φράσεις: \(x_1^{(C_1)}\)–\(\bar x_1^{(C_2)}\), \(x_1^{(C_1)}\)–\(\bar x_1^{(C_3)}\), \(x_3^{(C_1)}\)–\(\bar x_3^{(C_3)}\), \(x_3^{(C_2)}\)–\(\bar x_3^{(C_3)}\). Ανεξάρτητο σύνολο για \((1,0,1)\): οι ίδιες τρεις κορυφές (\(x_1\in C_1\), \(\bar x_2\in C_2\), \(\bar x_2\in C_3\)), μία από κάθε τρίγωνο και καμία ακμή «συγκρούσεων» μεταξύ τους.
VERTEX COVER (k' = 2·3 = 6 = 9 − 3): ίδιο γράφημα με το IS. Το συμπλήρωμα του ανεξάρτητου συνόλου, δηλαδή οι άλλες 6 κορυφές (\(\bar x_2,x_3\in C_1\)· \(\bar x_1,x_3\in C_2\)· \(\bar x_1,\bar x_3\in C_3\)), είναι κάλυψη κορυφών μεγέθους 6.
Ερώτηση 13¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
- «III και IV» (η ισοδυναμία CFG και η κενότητα ΤΜ είναι μη διαγνώσιμα· τα I και II είναι διαγνώσιμα).
- «Το σύνολο όλων των γλωσσών που ορίζονται στο Σ» (υπεραριθμήσιμο).
- «Το \(P_3\) είναι undecidable αν υπάρχει αναγωγή από το \(P_2\) στο \(P_3\)».
- «\(L_1-L_3\) είναι αναγνωρίσιμη» δεν είναι αναγκαστικά αληθής (\(L_1=\Sigma^*\) δίνει \(\overline{L_3}\), μη αναγνωρίσιμο).
- Ψευδείς είναι η 2η και η 4η επιλογή· η 2η όμως (όπως τυπώνεται, «Α διαγνώσιμη ⇒ Β μη διαγνώσιμη») φαίνεται τυπογραφικό λάθος για μια αληθή πρόταση, οπότε η αναμενόμενη απάντηση είναι πιθανότατα η 4η («\(B\) μη αναγνωρίσιμη ⇒ \(A\) μη αναγνωρίσιμη», ψευδής: π.χ. \(A=\varnothing\)).
- \(d(s)\bmod5=2\) και \(d(s)\bmod7\ne4\): ένα DFA με 35 καταστάσεις (υπόλοιπο mod 35) τα διαγιγνώσκει, άρα «Η L είναι κανονική».
- \(Y'\) (συμπλήρωμα της \(Y\)) είναι μη αναγνωρίσιμο και \(Y'\le W\) ⇒ η \(W\) δεν είναι αναγνωρίσιμη. Η \(X'\) είναι αναδρομική και \(Z\le X'\) ⇒ η \(Z\) είναι αναδρομική. «W όχι αναδρομικά αριθμήσιμη και Z αναδρομική».
- Η \(L\) είναι είτε \(\{0,1\}^*\) είτε \(\varnothing\) (ανάλογα με το αληθές ή ψευδές του \(P=NP\), που είναι μια σταθερά), και οι δύο είναι αναδρομικές· υπάρχει ΤΜ που διαγιγνώσκει την \(L\) (ακόμη κι αν δεν γνωρίζουμε ποια). «L είναι αναδρομική».