Θεωρία Υπολογισμού και Πολυπλοκότητα — Φεβρουάριος 2022 (στιγμιότυπα)

Μεταγραφή από τα στιγμιότυπα 136.png, 1643750780515696.jpg, Screenshot_20220202-033644_Chrome.jpg και tour.png, με τη σειρά που δείχνουν τις ερωτήσεις.

136.png

Δίνεται η γραμματική \(G=\{V, \Sigma, R, S\}\) με \(V=\{M, A\}\), \(\Sigma=\{a, b\}\), \(P=\{M \to aM \mid aA, A \to bA \mid b\}\), \(S=M\).

Ποια από τις παρακάτω κανονικές εκφράσεις περιγράφει τη L(G);

• [ ] (aUb)*
• [ ] a(ab)*b
• [ ] aabb
• [ ] ab

1643750780515696.jpg

1. Η κανονική έκφραση που περιγράφει

[Λείπει από τη φωτογραφία: τέλος της πρώτης γραμμής της διατύπωσης]

αναγνωρίζεται από το DFA του σχήματος

[Λείπει από τη φωτογραφία: τέλος της πρότασης]

[Σχήμα: Μέρος διαγράμματος DFA (το δεξιό τμήμα κόβεται από τη φωτογραφία). Αριστερά κατάσταση με βρόχο και δύο τόξα προς τα δεξιά προς κατάσταση διπλού κύκλου (τελική). Οι ετικέτες των μεταβάσεων είναι [δυσανάγνωστο].]

• [ ] (α) ab*(b|aab)
• [ ] (β) ab(b|aab)*
• [ ] (γ) ab(b |aa*b)

• [ ] (δ) ab(b | aab)

• Κανονική έκφραση για τη γλώσσα \(L = \{w\)

[Λείπει από τη φωτογραφία: το υπόλοιπο της πρώτης γραμμής της διατύπωσης (κόβεται από το δεξιό άκρο) και οι επιλογές απαντήσεων]

ζεύγος συνεχόμενων μηδενικών} είναι η

Screenshot_20220202-033644_Chrome.jpg

Ερώτηση 38. Συμπληρώστε χρησιμοποιώντας τη σταθερά p, που συμβολίζει το μέγιστο μήκος λέξης στη γλώσσα L. Πρόταση: Οι πεπερασμένες γλώσσες ικανοποιούν τετριμμένα το Pumping Lemma για μήκος λέξης \(n =\) _____

Ερώτηση 19 / 20 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός) Συμπληρώστε χρησιμοποιώντας τη σταθερά p, που συμβολίζει το μέγιστο μήκος λέξης στη γλώσσα L. Πρόταση: Οι πεπερασμένες γλώσσες ικανοποιούν τετριμμένα το Pumping Lemma για μήκος λέξης \(n =\) _____

• [ ] p
• [ ] p+1
• [ ] p-1
• [ ] Τίποτα από τα παραπάνω

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

tour.png

1. Ποια από τις παρακάτω μετατροπές δεν είναι δυνατή (αλγοριθμικά

[Λείπει από τη φωτογραφία: τέλος της διατύπωσης]

• [ ] (α) κανονική γραμματική σε γραμματική χωρίς συμφραζόμενα
• [ ] (β) μη ντετερμινιστικό πεπερασμένο αυτόματο σε ντετερμινιστικό πεπερασμένο αυτόματο
• [ ] (γ) μη ντετερμινιστικό αυτόματο στοίβας (PDA) σε ντετερμινιστικό αυτόματο στοίβας (PDA)
• [ ] (δ) μη ντετερμινιστική μηχανή Turing σε ντετερμινιστική μηχανή Turing

Λύσεις (🟡 community)

Κατάσταση: 🟡 community Πηγή: στιγμιότυπα οθόνης πλατφόρμας ερωτήσεων με εμφανιζόμενες απαντήσεις (φοιτητικές λήψεις, Discord 2022-02-01 έως 2022-02-02)

Προσοχή

Ερώτηση 2 (tour.png): η απάντηση «(α) κανονική γραμματική σε γραμματική χωρίς συμφραζόμενα» δεν είναι σωστή, γιατί κάθε κανονική γλώσσα παράγεται από γραμματική χωρίς συμφραζόμενα, άρα η μετατροπή είναι πάντα δυνατή. Η μετατροπή που δεν είναι αλγοριθμικά δυνατή είναι η (γ) (μη ντετερμινιστικό PDA σε ντετερμινιστικό PDA). Ερώτηση 16 (1643750780515696.jpg): η πλατφόρμα χαρακτηρίζει λάθος την (δ) και δίνει ως σωστή την (β) ab(b|aab). Η (δ) ab(b*|aab) όμως είναι ισοδύναμη με την (β), αφού το (b*|aab) παράγει τις ίδιες λέξεις με το (b|aab). Το ίδιο ζήτημα τέθηκε στο Discord (2022-02-01). Το διάγραμμα DFA δεν φαίνεται ολόκληρο στη φωτογραφία, οπότε η (β) δεν επαληθεύεται από αυτή. Ερώτηση 136 (136.png): η εικόνα δίνει δύο απαντήσεις (Απάντηση 1: A, Απάντηση 2: C). Η σωστή είναι η C (aabb), γιατί η L(G) είναι η a⁺b⁺. Η A, (aUb)*, δεν περιγράφει τη γλώσσα.

Λύσεις — Θεωρία Υπολογισμού και Πολυπλοκότητας — Φεβρουάριος 2022

Απαντήσεις όπως εμφανίζονται στα στιγμιότυπα, με τη σειρά των αρχείων. Το κείμενο των ερωτήσεων προέρχεται από τις μεταγραφές και δεν έχει ελεγχθεί. Ο έλεγχος των απαντήσεων σημειώνεται στα warnings.

136.png

Δίνεται η γραμματική \(G=\{V, \Sigma, R, S\}\) με \(V=\{M, A\}\), \(\Sigma=\{a, b\}\), \(P=\{M \to aM \mid aA, A \to bA \mid b\}\), \(S=M\).

Ποια από τις παρακάτω κανονικές εκφράσεις περιγράφει τη L(G);

• [ ] (aUb)*
• [ ] a(ab)*b
• [ ] aabb
• [ ] ab

Απάντηση 1 : A

Απάντηση 2 : C

1643750780515696.jpg

1. Η κανονική έκφραση που περιγράφει [τη γλώσσα που] αναγνωρίζεται από το DFA του σχήματος [είναι:]

[Σχήμα: Διάγραμμα καταστάσεων DFA με 2 καταστάσεις. Η αριστερή αρχική κατάσταση έχει βρόχο με 'a' και μετάβαση προς τα δεξιά με 'b'. Η δεξιά είναι τελική κατάσταση (διπλός κύκλος) με βρόχο 'b' και μετάβαση προς τα αριστερά με 'a'.]

• [ ] (α) ab*(b|aab)
• [ ] (β) ab(b|aab)*
• [ ] (γ) ab(b |aa*b)
• [ ] (δ) ab(b | aab)

Απάντηση (δ) ab(b | aab) Λάθος. Σωστή απάντηση (β) ab(b|aab)*

1. Κανονική έκφραση για τη γλώσσα \(L = \{w \ldots \text{ ζεύγος συνεχόμενων μηδενικών}\}\) είναι η

Screenshot_20220202-033644_Chrome.jpg

Ερώτηση 38. Συμπληρώστε χρησιμοποιώντας τη σταθερά p, που συμβολίζει το μέγιστο μήκος λέξης στη γλώσσα L. Πρόταση: Οι πεπερασμένες γλώσσες ικανοποιούν τετριμμένα το Pumping Lemma για μήκος λέξης \(n =\) _____

Ερώτηση 19 / 20 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός) Συμπληρώστε χρησιμοποιώντας τη σταθερά p, που συμβολίζει το μέγιστο μήκος λέξης στη γλώσσα L. Πρόταση: Οι πεπερασμένες γλώσσες ικανοποιούν τετριμμένα το Pumping Lemma για μήκος λέξης \(n =\) _____

• [ ] p
• [ ] p+1
• [ ] p-1
• [ ] Τίποτα από τα παραπάνω

Απάντηση 38 : B

tour.png

1. Ποια από τις παρακάτω μετατροπές δεν είναι δυνατή (αλγοριθμικά

(α) κανονική γραμματική σε γραμματική χωρίς συμφραζόμενα (β) μη ντετερμινιστικό πεπερασμένο αυτόματο σε ντετερμινιστικό πεπερασμένο αυτόματο (γ) μη ντετερμινιστικό αυτόματο στοίβας (PDA) σε ντετερμινιστικό αυτόματο στοίβας (PDA) (δ) μη ντετερμινιστική μηχανή Turing σε ντετερμινιστική μηχανή Turing

Απάντηση (α) κανονική γραμματική σε γραμματική χωρίς συμφραζόμενα

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

---

✖ Βρήκα λάθος στη μεταγραφή