Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Φεβρουάριος 2021 — Θέμα 1¶
Μεταγραφή από τη φωτογραφία 2024-09-24_4.38.35_.png (το όνομα αρχείου είναι ημερομηνία λήψης). Η φωτογραφία φέρει τον τίτλο που φαίνεται παρακάτω, αλλά δεν περιέχει λύσεις.
2024-09-24_4.38.35_.png¶
ΘΕΜΑΤΑ ΚΑΙ ΛΥΣΕΙΣ ΑΡΧΕΣ ΓΛΩΣΣΩΝ ΦΕΒΡΟΥΑΡΙΟΣ 2021
1) Δίνεται η BNF γραμματική στο τέλος της εκφώνησης με επτά κανόνες R1-R7 και τερματικά σύμβολα 0 1
Α) Τί τύπου είναι η γραμματική στην ιεραρχία Chomsky. Αιτιολογήστε την απάντησή σας.
Β) Τι είδους συμβολοσειρές περιγράφει η παραπάνω γραμματική;
Γ) Μπορείτε να φτιάξετε μία κανονική έκφραση αντίστοιχη της γραμματικής και γιατί; Αν ναι παρουσιάστε την.
Δ) Ελέγξτε αν η συμβολοσειρά 011101 είναι μέλος της γλώσσας παρουσιάζοντας την δημιουργία της top-down συντακτικής ανάλυσης της συμβολοσειράς, με τον παρακάτω τρόπο: S0->[R1]0S1->[R2] 0.S2->[R3] 0.0S3->[R6] 0.01
R1,R2: <S>::= 0 <S>|1<A>
R3,R4: <A>::= 0 <S> |1<B>
R5,R6, R7: <B>::= 0 <B>|1< B>| $\epsilon$
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-02¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Η γραμματική (όπως στην εκφώνηση): R1: \(S\to 0S\), R2: \(S\to 1A\), R3: \(A\to 0S\), R4: \(A\to 1B\), R5: \(B\to 0B\), R6: \(B\to 1B\), R7: \(B\to\epsilon\).
Α) Τύπος: κάθε κανόνας έχει ένα τερματικό ακολουθούμενο από το πολύ ένα μη τερματικό (ή \(\epsilon\)): δεξιά γραμμική γραμματική ⇒ Τύπου 3 (κανονική).
Β) Γλώσσα: το \(S\) διαβάζει 0 (μένει) ή 1 (πάει στο \(A\)). Το \(A\) με 0 γυρνά στο \(S\) (το 1 ακυρώθηκε), με 1 πάει στο \(B\) (δύο διαδοχικά 1). Το \(B\) δέχεται οτιδήποτε και τελειώνει με \(\epsilon\). Άρα: οι δυαδικές συμβολοσειρές που περιέχουν τουλάχιστον δύο διαδοχικά 1 (υποσυμβολοσειρά 11). Ελάχιστη: 11.
Γ) Κανονική έκφραση: ναι, γιατί η γραμματική είναι Τύπου 3 (κανονική γλώσσα). Πριν το πρώτο 11 κάθε 1 πρέπει να ακολουθείται από 0:
(Έλεγχος με πρόγραμμα σε όλες τις συμβολοσειρές μέχρι μήκος 12: ταυτίζεται με «περιέχει 11».)
Δ) Top-down παραγωγή της 011101:
\(S_0 \to[R1]\ 0S_1 \to[R2]\ 01A_2 \to[R4]\ 011B_3 \to[R6]\ 0111B_4 \to[R5]\ 01110B_5 \to[R6]\ 011101B_6 \to[R7]\ 011101\)
Με τον τρόπο της εκφώνησης: \(S_0\to[R1]\,0S_1\to[R2]\,0.1A_2\to[R4]\,0.1.1B_3\to[R6]\,0.1.1.1B_4\to[R5]\,0.1.1.1.0B_5\to[R6]\,0.1.1.1.0.1B_6\to[R7]\,011101\).
Η είσοδος καταναλώνεται πλήρως και φτάνουμε σε \(\epsilon\) ⇒ η 011101 είναι μέλος της γλώσσας.