Θεωρία Υπολογισμού και Πολυπλοκότητα — Ιούνιος 2025 (26/6/2025)¶
Μεταγραφή από τις φωτογραφίες IMG_20250626_153109.jpg, IMG_20250626_150526.jpg και IMG_20250626_154726.jpg, με βοήθημα την 3.jpg.
IMG_20250626_153109.jpg¶
ΠΕΜΠΤΗ, 26 ΙΟΥΝΙΟΥ 2025 CEID_24Y301, ΧΡ. ΚΑΚΛΑΜΑΝΗΣ, Ε. ΠΑΠΑΪΩΑΝΝΟΥ
ΕΡΩΤΗΣΗ 3 [2 ΜΟΝΑΔΕΣ] Ποιο είναι το ελάχιστο πλήθος καταστάσεων σε DFA που αναγνωρίζει τη γλώσσα:
| Γλώσσα | Ελάχιστο πλήθος καταστάσεων |
|---|---|
| [1/2] ${w_1 a w_2 \mid w_1, w_2 \in {a,b}^*, | w_1 |
| [1/2] \(\{w \in \{a,b\}^* \mid \text{για κάθε a που περιέχεται στη w προηγείται και έπεται ένα b}\}\) | |
| [1/2] \(\{w \in \{0,1\}^* \mid \eta\ w\ \text{ξεκινάει με 0 και έχει περιττό μήκος ή ξεκινάει με 1 και έχει άρτιο μήκος}\}\) | |
| [1/2] \(\{a^{nk} \mid k>0, \text{n θετική ακέραια σταθερά}\}\) |
ΕΡΩΤΗΣΗ 4 [1 ΜΟΝΑΔΑ] [1/2] Η γλώσσα \(\{1^k y \mid k \ge 1, y \in \{0,1\}^* \text{ και η y περιέχει τουλάχιστον (A) /το πολύ (B) } k \text{ "1"}\}\) είναι κανονική (1) / δεν είναι κανονική (2). Επιλέξτε τους σωστούς συνδυασμούς: - [ ] A-1 - [ ] A-2 - [ ] B-1 - [ ] B-2
[1/2] Δίνεται η γλώσσα \(T = \{x w x^R \mid x, w \in (0 \cup 1)^* - \{\varepsilon\}\}\). Είναι η Τ κανονική; (\(s^R\): η αντίστροφη λέξη της s) Αν ναι, δώστε κανονική έκφραση: _______________ Αν όχι, δώστε λέξη για την εφαρμογή του Pumping Lemma (καλούμε p τη σταθερά) \(w =\) _______________ και πλήθος επαναλήψεων \(i =\) _______________ του μεσαίου τμήματος που οδηγεί στην παραγωγή λέξης που δεν ανήκει στη δοσμένη γλώσσα.
ΕΡΩΤΗΣΗ 5 [1 ΜΟΝΑΔΑ] [1] Μετατρέψτε το NFA του σχήματος σε ισοδύναμο DFA χρησιμοποιώντας την κατασκευαστική μέθοδο πο[δυσανάγνωστο] υποσυνόλων (subset construction).
[Λείπει από τη φωτογραφία: το σχήμα του NFA]
IMG_20250626_150526.jpg¶
ΠΕΜΠΤΗ, 26 ΙΟΥΝΙΟΥ 2025 CEID_24Y301, ΧΡ. ΚΑΚΛΑΜΑΝΗΣ, Ε. ΠΑΠΑΪΩΑΝΝΟΥ
ΕΡΩΤΗΣΗ 7 [3 ΜΟΝΑΔΕΣ] Δώστε CFG με το πλήθος μεταβλητών που υποδεικνύεται για τις γλώσσες:
| Γλώσσα | CFG |
|---|---|
| [1] \(\{w \in \{a,b,c\}^* \mid \#c(w) = \#a(w) + \#b(w)\}\) 1 μεταβλητή |
|
| [1] \(\{x \in (0 \cup 1)^* \mid x \ne ww \text{ για κάθε } w \in (0 \cup 1)^*\}\) 3 μεταβλητές |
|
| [1] \(\{a^n b^m \mid m \ge n, m-n \text{ περιττός}\}\) 1 μεταβλητή |
ΕΡΩΤΗΣΗ 8 [1 ΜΟΝΑΔΑ] [1] Δώστε διάγραμμα καταστάσεων με 3 καταστάσεις για μη ντετερμινιστικό αυτόματο στοίβας (nPDA) για τη γλώσσα που είναι ορισμένη στο αλφάβητο \(\{a,b\}\) και περιέχει λέξεις με ίσο πλήθος a και b.
ΕΡΩΤΗΣΗ 9 [1 ΜΟΝΑΔΑ] Σημειώστε με X όταν η γλώσσα είναι χωρίς συμφραζόμενα (CFL), αφήστε κενό διαφορετικά (\(x^R\): λέξη αντίστροφη (reverse) της x)
| γλώσσα | γλώσσα είναι χωρίς συμφραζόμενα (CFL); |
|---|---|
| [1/5] \(\{a^n b^n \mid n \ge 0, n \notin [157, 253]\}\) | |
| [1/5] \(\{0^i 1^j 0^i 1^j \mid i,j > 0\}\) | |
| [1/5] \(\{a^i b^j c^i d^j \mid i,j \ge 0\}\) | |
| [1/5] \(\{w w^R w \mid w \in \{0,1\}^*\}\) | |
| [1/5] \(\{0^i 1^j 0^i 1^k 0^k 1^i \mid i,j,k > 0\}\) |
ΕΡΩΤΗΣΗ 10 [1 ΜΟΝΑΔΑ] [1] Δώστε διάγραμμα καταστάσεων με 5 καταστάσεις για μηχανή Turing για τη συνάρτηση
[Λείπει από τη φωτογραφία: ο τύπος της συνάρτησης]
Λάβετε υπόψιν ότι τα x και y δίνονται σε μοναδιαία αναπαράσταση χωρισμένα με 0.
IMG_20250626_154726.jpg¶
ΠΕΜΠΤΗ, 26 ΙΟΥΝΙΟΥ 2025 CEID_24Y301, ΧΡ. ΚΑΚΛΑΜΑΝΗΣ, Ε. ΠΑΠΑΪΩΑΝΝΟΥ
ΕΡΩΤΗΣΗ 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
[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 είναι γλώσσες τέτοιες ώστε να υπάρχει [συμπληρώθηκε από Screenshot_2026-06-22_195210.png: αναγωγή από την Y' στη W και από τη Z στη X'. Ποια από τις προτάσεις είναι αληθής;] (X', Y': συμπληρωματικές γλώσσες των X και Y, αντίστοιχα)
[Λείπει από τη φωτογραφία: οι επιλογές απάντησης]
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2025-06.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):3.jpg(διπλότυπο της σελίδας των Ερωτήσεων 7–10, χρησιμοποιήθηκε για έλεγχο)
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2025-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 3¶
Αξιοπιστία: ⚠ οι ανεξάρτητες λύσεις διαφωνούν: δες όλες και έλεγξε μόνος σου · εμπιστοσύνη λύτη: χαμηλή
Λύση 1: 1. \(\{w_1aw_2: |w_1|=2,|w_2|\ge3\}\): λέξεις μήκους \(\ge6\) με το 3ο σύμβολο \(a\). Καταστάσεις: μετρητής θέσης 0,1,2 (3), μετά το 3ο σύμβολο \(a\) μετράμε 0,1,2,≥3 επιπλέον σύμβολα (4), και παγίδα αν το 3ο είναι \(b\) (1). 8. 2. «Για κάθε \(a\) προηγείται και έπεται \(b\)» (ερμηνεία: ακριβώς δίπλα): η λέξη δεν αρχίζει με \(a\), δεν τελειώνει με \(a\) και δεν περιέχει \(aa\). Καταστάσεις: αρχική (αποδέχεται το \(\varepsilon\), δεν επιτρέπεται \(a\)), μετά από \(b\) (τελική), μετά από \(a\) (μη τελική, πρέπει \(b\)), παγίδα. 4. Αν η εκφώνηση εννοεί «κάπου πριν και κάπου μετά» το αποτέλεσμα θα διέφερε· χρειάζεται έλεγχος με το πρωτότυπο. 3. «αρχίζει με 0 και περιττό μήκος ή με 1 και άρτιο μήκος»: καταστάσεις αρχική, «τελική-ισοτιμία» \(A\) (π.χ. μετά από 0 με περιττό μήκος ή 1 με άρτιο), «μη τελική-ισοτιμία» \(B\). Μεταβάσεις: αρχική:0→\(A\), 1→\(B\)· \(A\):0,1→\(B\)· \(B\):0,1→\(A\). 3. 4. \(\{a^{nk}: k>0\}\) με \(n\) σταθερά: πολλαπλάσια του \(n\), κύκλος \(n\) καταστάσεων. \(n\).
Λύση 2: 1. Γλώσσα \(\{w_1 a w_2 \mid w_1, w_2 \in \{a,b\}^*, |w_1|=2, |w_2| \ge 3\}\): - Ελάχιστο πλήθος καταστάσεων: 8 - Αιτιολόγηση: Η γλώσσα περιγράφει λέξεις μήκους τουλάχιστον \(2 + 1 + 3 = 6\), όπου το 3ο σύμβολο είναι υποχρεωτικά 'a'. - Κατάσταση \(q_0\) (μήκος 0). - Κατάσταση \(q_1\) (μήκος 1). - Κατάσταση \(q_2\) (μήκος 2). - Αν στο \(q_2\) διαβαστεί 'a', πάμε στην κατάσταση \(q_3\) (μήκος 3, 3ο σύμβολο 'a'). Αν διαβαστεί 'b', η λέξη απορρίπτεται και οδηγείται σε κατάσταση παγίδα (trap state) \(q_{trap}\). - Από το \(q_3\), διαβάζοντας οποιοδήποτε σύμβολο (\(a\) ή \(b\)), πάμε στην \(q_4\) (μήκος 4). - Από το \(q_4\), με οποιοδήποτε σύμβολο, πάμε στην \(q_5\) (μήκος 5). - Από το \(q_5\), με οποιοδήποτε σύμβολο, πάμε στην τελική κατάσταση \(q_6\) (μήκος \(\ge 6\)), η οποία έχει βρόχο προς τον εαυτό της για κάθε είσοδο. - Συνολικά απαιτούνται οι καταστάσεις \(\{q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_{trap}\}\), δηλαδή 8 καταστάσεις. Όλες είναι ισοδύναμα διακριτές κατά Myhill-Nerode.
- Γλώσσα \(\{w \in \{a,b\}^* \mid \text{για κάθε a που περιέχεται στη w προηγείται και έπεται ένα b}\}\):
- Ελάχιστο πλήθος καταστάσεων: 4
-
Αιτιολόγηση: Κάθε εμφάνιση του 'a' πρέπει να βρίσκεται αυστηρά ανάμεσα σε δύο 'b' (δηλαδή κάθε 'a' περιβάλλεται από 'b', άρα δεν μπορεί να είναι στην αρχή, ούτε στο τέλος, ούτε να υπάρχουν διαδοχικά 'a'). Κανονική έκφραση: \(b^*(b a b^+)^* = b^*(a b^+)^* = \varepsilon \cup b(b \cup ab)^*\).
- \(q_0\) (αρχική, αποδεκτή): έχουμε δει μόνο \(b\) ή κενό (\(\varepsilon\)).
- Αν διαβαστεί 'a' από το \(q_0 \to\) αποτυχία (trap state \(q_{trap}\)), γιατί δεν προηγείται 'b'.
- Αν διαβαστεί 'b' από το \(q_0 \to q_1\) (αποδεκτή, το προηγούμενο σύμβολο ήταν 'b').
- Από το \(q_1\): με 'b' παραμένει στο \(q_1\). Με 'a' μεταβαίνει στο \(q_2\) (μη αποδεκτή, καθώς το 'a' περιμένει το υποχρεωτικό επόμενο 'b').
- Από το \(q_2\): με 'b' πάει στο \(q_1\) (εκπληρώθηκε η απαίτηση). Με 'a' πάει στο \(q_{trap}\) (δύο διαδοχικά 'a').
- Το \(q_{trap}\) (μη αποδεκτή παγίδα) με 'a','b' παραμένει στο \(q_{trap}\).
- Σύνολο καταστάσεων: \(\{q_0, q_1, q_2, q_{trap}\}\), δηλαδή 4 καταστάσεις (και το \(\varepsilon\) ανήκει στη γλώσσα, αφού ικανοποιεί κενά την απαίτηση).
-
Γλώσσα \(\{w \in \{0,1\}^* \mid \eta\ w\ \text{ξεκινάει με 0 και έχει περιττό μήκος ή ξεκινάει με 1 και έχει άρτιο μήκος}\}\):
- Ελάχιστο πλήθος καταστάσεων: 5
-
Αιτιολόγηση:
- \(q_0\) (αρχική, μη αποδεκτή, μήκος 0).
- Με 0: πάει στην \(q_{0,odd}\) (ξεκίνησε με 0, μήκος 1 \(\to\) περιττό, αποδεκτή).
- Με 1: πάει στην \(q_{1,odd}\) (ξεκίνησε με 1, μήκος 1 \(\to\) περιττό, μη αποδεκτή).
- Από \(q_{0,odd}\) με \(0,1 \to q_{0,even}\) (ξεκίνησε με 0, άρτιο μήκος, μη αποδεκτή).
- Από \(q_{0,even}\) με \(0,1 \to q_{0,odd}\) (ξεκίνησε με 0, περιττό μήκος, αποδεκτή).
- Από \(q_{1,odd}\) με \(0,1 \to q_{1,even}\) (ξεκίνησε με 1, άρτιο μήκος, αποδεκτή).
- Από \(q_{1,even}\) με \(0,1 \to q_{1,odd}\) (ξεκίνησε με 1, περιττό μήκος, μη αποδεκτή).
- Οι καταστάσεις είναι 5: \(\{q_0, q_{0,odd}, q_{0,even}, q_{1,odd}, q_{1,even}\}\) και είναι όλες μη ισοδύναμες μεταξύ τους.
-
Γλώσσα \(\{a^{nk} \mid k>0, \text{n θετική ακέραια σταθερά}\}\):
- Ελάχιστο πλήθος καταστάσεων: \(n+1\)
- Αιτιολόγηση: Η γλώσσα περιλαμβάνει λέξεις \(a^m\) όπου \(m\) είναι θετικό πολλαπλάσιο του \(n\) (\(m \in \{n, 2n, 3n, \dots\}\)). Επειδή \(k > 0\), η κενή λέξη \(\varepsilon = a^0\) δεν ανήκει στη γλώσσα. Επομένως, η αρχική κατάσταση (μήκος 0) δεν μπορεί να είναι αποδεκτή, ενώ η κατάσταση για μήκος \(n \pmod n = 0\) μετά από τουλάχιστον ένα βήμα πρέπει να είναι αποδεκτή. Αυτό απαιτεί \(n\) καταστάσεις για τον κύκλο modulo \(n\) συν 1 αρχική κατάσταση (ή ισοδύναμα, \(q_0 \xrightarrow{a} q_1 \xrightarrow{a} \dots \xrightarrow{a} q_n\) όπου \(q_n\) είναι αποδεκτή και με \(a\) μεταβαίνει στο \(q_1\)). Άρα συνολικά \(n+1\) καταστάσεις.
Λύση 3 (τρίτη γνώμη): ### 1. Γλώσσα \(\{w_1 a w_2 \mid w_1, w_2 \in \{a,b\}^*, |w_1|=2, |w_2| \ge 3\}\) - Ελάχιστο πλήθος καταστάσεων: 8 - Αιτιολόγηση: Οι αποδεκτές λέξεις έχουν μήκος τουλάχιστον \(2 + 1 + 3 = 6\) με το 3ο σύμβολο να είναι 'a'. Χρειαζόμαστε καταστάσεις για τα μήκη 0, 1, 2 (\(q_0, q_1, q_2\)). Στην \(q_2\), με 'a' μεταβαίνει στην \(q_3\) ενώ με 'b' απορρίπτει στην κατάσταση-παγίδα \(q_{\text{trap}}\). Από την \(q_3\) απαιτούνται τουλάχιστον 3 επιπλέον σύμβολα, οπότε ακολουθούν οι \(q_4, q_5\) και η τελική αποδεκτή κατάσταση \(q_6\) (με αυτοβρόχο για \(a, b\)). Σύνολο: \(\{q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_{\text{trap}}\} \implies \mathbf{8}\) καταστάσεις (όλες διακριτές κατά Myhill-Nerode).
2. Γλώσσα \(\{w \in \{a,b\}^* \mid \text{για κάθε a που περιέχεται στη w προηγείται και έπεται ένα b}\}\)¶
- Ελάχιστο πλήθος καταστάσεων: 4
- Αιτιολόγηση: Κάθε 'a' πρέπει να περιβάλλεται αυστηρά από 'b' (ούτε στην αρχή, ούτε στο τέλος, ούτε διαδοχικά 'aa'). Η κενή λέξη \(\varepsilon\) ανήκει στη γλώσσα (κενή ικανοποίηση συνθήκης).
- \(q_0\) (αρχική, αποδεκτή): κενή λέξη. Με 'b' πάει στην \(q_1\), με 'a' στην \(q_{\text{trap}}\).
- \(q_1\) (αποδεκτή): τελευταίο σύμβολο ήταν 'b'. Με 'b' παραμένει στην \(q_1\), με 'a' πάει στην \(q_2\).
- \(q_2\) (μη αποδεκτή): διαβάστηκε 'a' (που προηγήθηκε 'b' και περιμένει 'b'). Με 'b' επιστρέφει στην \(q_1\), με 'a' πάει στην \(q_{\text{trap}}\).
- \(q_{\text{trap}}\) (μη αποδεκτή παγίδα). Σύνολο: \(\{q_0, q_1, q_2, q_{\text{trap}}\} \implies \mathbf{4}\) καταστάσεις.
3. Γλώσσα \(\{w \in \{0,1\}^* \mid \eta\ w\ \text{ξεκινάει με 0 και έχει περιττό μήκος ή ξεκινάει με 1 και έχει άρτιο μήκος}\}\)¶
- Ελάχιστο πλήθος καταστάσεων: 3
- Αιτιολόγηση: Η κενή λέξη απορρίπτεται στην αρχική κατάσταση \(q_0\).
- Μετά από 0, μια λέξη γίνεται δεκτή αν και μόνο αν το υπόλοιπο μήκος είναι άρτιο (ώστε συνολικό μήκος περιττό).
- Μετά από 1, μια λέξη γίνεται δεκτή αν και μόνο αν το υπόλοιπο μήκος είναι περιττό (ώστε συνολικό μήκος άρτιο). Συνεπώς, μετά το 1ο σύμβολο υπάρχουν μόνο δύο κλάσεις ισοδυναμίας Myhill-Nerode:
- Κατάσταση \(A\) (αποδεκτή): αποδέχεται επεκτάσεις αρτίου μήκους.
- Κατάσταση \(B\) (μη αποδεκτή): αποδέχεται επεκτάσεις περιττού μήκους. Μεταβάσεις: \(\delta(q_0, 0) = A\), \(\delta(q_0, 1) = B\), και για κάθε είσοδο \(\delta(A, 0) = \delta(A, 1) = B\), \(\delta(B, 0) = \delta(B, 1) = A\). Σύνολο: \(\{q_0, A, B\} \implies \mathbf{3}\) καταστάσεις.
4. Γλώσσα \(\{a^{nk} \mid k>0, \text{n θετική ακέραια σταθερά}\}\)¶
- Ελάχιστο πλήθος καταστάσεων: n + 1
- Αιτιολόγηση: Επειδή \(k > 0\), η κενή λέξη \(a^0 = \varepsilon\) δεν ανήκει στη γλώσσα. Άρα η αρχική κατάσταση \(q_0\) (μήκος 0) είναι μη αποδεκτή. Αντίθετα, η κατάσταση για μήκος \(n\) είναι αποδεκτή. Οι συμβολοσειρές \(\{a^0, a^1, \dots, a^{n-1}, a^n\}\) είναι όλες ανά δύο διακριτές κατά Myhill-Nerode (π.χ. για \(a^0\) η κατάληξη \(a^0\) απορρίπτεται ενώ για \(a^n\) γίνεται δεκτή). Απαιτούνται \(n\) καταστάσεις για τον κύκλο \(\pmod n\) (\(q_1, \dots, q_n\)) συν την ξεχωριστή αρχική κατάσταση \(q_0\), άρα συνολικά \(\mathbf{n+1}\) καταστάσεις.
Συνολικά σωστές απαντήσεις: 8, 4, 3, n+1. Η λύση Α ελαχιστοποίησε σωστά το 3ο ερώτημα (3 καταστάσεις), αλλά έσφαλε στο 4ο δίνοντας \(n\) αντί για \(n+1\) αγνοώντας τον περιορισμό \(k>0\), ενώ η λύση Β βρήκε σωστά το \(n+1\) στο 4ο, αλλά παρέλειψε να ελαχιστοποιήσει το 3ο ερώτημα (δίνοντας 5 αντί για 3 καταστάσεις).
Θέμα 4 (α)¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Ισχύει ότι \(w\in A\iff w\) αρχίζει με 1 και περιέχει ≥2 «1» συνολικά. Πράγματι, για \(w=1^k y\) με \(k\le L\) (\(L\) το πλήθος των αρχικών 1) και \(T\) το συνολικό πλήθος 1: το \(y\) έχει \(T-k\) «1»· υπάρχει \(k\in[1,L]\) με \(T-k\ge k\) ανν \(L\ge1\) και \(T\ge2\) (επιλέγουμε \(k=1\)). Άρα η \(A\) είναι κανονική (A-1), ενώ η \(B\) (\(\,w\in B\iff 1\le L\) και \(2L\ge T\)) όχι: οι λέξεις \(1^m0\) έχουν ανά δύο διαφορετικές κλάσεις (η \(1^m01^m\in B\), η \(1^{m'}01^m\notin B\) για \(m'<m\) ), οπότε απαιτούνται άπειρες καταστάσεις (B-2). Επαληθεύτηκε ότι το πλήθος των κλάσεων μεγαλώνει με το μήκος.
Σωστός συνδυασμός: A-1 και B-2.
Θέμα 4 (β)¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
\(T=\{xwx^R: x,w\ne\varepsilon\}\) είναι κανονική: για \(x=c\) (ένα σύμβολο) έχουμε τις λέξεις \(c\,w\,c\) με \(w\ne\varepsilon\)· για μεγαλύτερο \(x\) η λέξη αρχίζει και τελειώνει στο ίδιο σύμβολο (πρώτο γράμμα του \(x\)) και έχει μήκος \(\ge3\). Άρα $\(T=0(0\cup1)^+0\ \cup\ 1(0\cup1)^+1.\)$ Επαληθεύτηκε εξαντλητικά έως μήκος 11.
Θέμα 5¶
Αξιοπιστία: δεν λύθηκε
Δεν λύθηκε: λείπει το σχήμα του NFA (και τμήμα της διατύπωσης).
Θέμα 7¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
- \(\{w:\#c=\#a+\#b\}\), μία μεταβλητή: \(S\to aSc\,S\mid bSc\,S\mid cSa\,S\mid cSb\,S\mid\varepsilon\). Αιτιολόγηση: αν η \(w\) έχει συνολικό «βάρος» 0 (\(a,b\): +1, \(c\): −1) και αρχίζει με \(a\) ή \(b\), η πρώτη επιστροφή του μερικού αθροίσματος στο 0 γράφει \(w=p\,u\,c\,v\) με \(u,v\) βάρους 0· συμμετρικά αν αρχίζει με \(c\). Επαληθεύτηκε με παραγωγή για μήκη ≤8.
- \(\{x\in\{0,1\}^*: x\ne ww\}\), τρεις μεταβλητές: \(S\to AB\mid BA\mid A\mid B\), \(A\to 0A0\mid0A1\mid1A0\mid1A1\mid 0\), \(B\to 0B0\mid0B1\mid1B0\mid1B1\mid 1\). Η \(A\) παράγει τις λέξεις περιττού μήκους με μεσαίο σύμβολο 0, η \(B\) με μεσαίο 1. Οι \(A\cup B\) είναι όλες οι λέξεις περιττού μήκους (δεν είναι τετράγωνα). Στο \(AB\) το «0» και το «1» απέχουν ακριβώς το μισό μήκος, άρα η λέξη έχει διαφορά ανάμεσα στις δύο μισές (μη τετράγωνο)· και κάθε άρτιου μήκους μη τετράγωνο έχει τέτοια θέση. Επαληθεύτηκε για μήκη ≤12.
- \(\{a^nb^m: m\ge n,\ m-n\text{ περιττός}\}\), μία μεταβλητή: \(S\to aSb\mid Sbb\mid b\). Παράγει \(a^nb^{n+2j+1}\). Επαληθεύτηκε.
Θέμα 8¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
nPDA με 3 καταστάσεις \(q_0\) (αρχική), \(q_1\), \(q_2\) (τελική). Μεταβάσεις (σύμβολο εισόδου, κορυφή στοίβας → νέα στοίβα): - \(q_0\to q_1\): \(\varepsilon,\varepsilon\to\$\) - \(q_1\) βρόχοι: \(a,\$\to A\$\)· \(a,A\to AA\)· \(a,B\to\varepsilon\)· \(b,\$\to B\$\)· \(b,B\to BB\)· \(b,A\to\varepsilon\) - \(q_1\to q_2\): \(\varepsilon,\$\to\varepsilon\)
Η στοίβα κρατά την πλεονάζουσα μεγαλύτερη ποσότητα (\(A\) για επιπλέον \(a\), \(B\) για επιπλέον \(b\)). Η λέξη γίνεται δεκτή ανν η στοίβα φτάσει στο \(\$\) στο τέλος. Επαληθεύτηκε με πρόγραμμα.
Θέμα 9¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
- \(\{a^nb^n:n\ge0,n\notin[157,253]\}\): CFL (X): το \(a^nb^n\) τομή με το κανονικό συμπλήρωμα του πεπερασμένου ευρετηρίου, ή γραμματική με κανόνες που αποκλείουν το διάστημα.
- \(\{0^i1^j0^i1^j\}\): όχι CFL (λήμμα άντλησης· οι εξαρτήσεις διασταυρώνονται).
- \(\{a^ib^jc^id^j\}\): όχι CFL (διασταυρούμενες εξαρτήσεις \(a\)–\(c\) και \(b\)–\(d\)).
- \(\{ww^Rw\}\): όχι CFL (η λέξη \(0^p1^p1^p0^p0^p1^p\) δεν αντλείται).
- \(\{0^i1^j0^i1^k0^k1^i\}\): όχι CFL (συσχετίσεις \(i\), \(i\) και \(k\), \(k\) διασταυρώνονται με το τελικό \(1^i\)).
Θέμα 10¶
Αξιοπιστία: δεν λύθηκε
Δεν λύθηκε: λείπει ο τύπος της συνάρτησης.
Θέμα 13¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στη φωτογραφία IMG_20250626_154726.jpg οι επιλογές απάντησης της υποερώτησης έχουν αποκοπεί στο κάτω άκρο της σελίδας, ωστόσο η διατύπωση και οι επιλογές ταυτίζονται πλήρως με την αντίστοιχη ερώτηση της εξέτασης 2026-06 (Screenshot_2026-06-22_195210.png).
Επιλογή: «W όχι αναδρομικά αριθμήσιμη (recursively enumerable) και Z αναδρομική (recursive)»
Αιτιολόγηση: 1. Η γλώσσα \(X\) είναι αναδρομική (recursive / decidable), άρα και το συμπλήρωμά της \(X'\) είναι αναδρομική γλώσσα (η κλάση των αναδρομικών γλωσσών είναι κλειστή ως προς το συμπλήρωμα). 2. Δίνεται ότι υπάρχει αναγωγή από τη \(Z\) στη \(X'\) (\(Z \le_m X'\)). Εφόσον η \(X'\) είναι αναδρομική, έπεται άμεσα ότι και η \(Z\) είναι αναδρομική. 3. Η γλώσσα \(Y\) είναι αναδρομικά αριθμήσιμη (recursively enumerable / RE) αλλά όχι αναδρομική. Συνεπώς, το συμπλήρωμά της \(Y'\) δεν είναι αναδρομικά αριθμήσιμη (αν ήταν RE, τότε επειδή και η \(Y\) είναι RE, η \(Y\) θα ήταν αναδρομική, άτοπο). 4. Δίνεται αναγωγή \(Y' \le_m W\). Αν η \(W\) ήταν αναδρομικά αριθμήσιμη, τότε μέσω της αναγωγής θα ήταν και η \(Y'\) αναδρομικά αριθμήσιμη, άτοπο. Επομένως, η \(W\) δεν είναι αναδρομικά αριθμήσιμη (όχι RE).