Αυτόματα – Τυπικές Γλώσσες – Υπολογισιμότητα

2.6 Ισοδυναμία κανονικών εκφράσεων και αυτομάτων

Στη συνέχεια θα αποδείξουμε οτι οι τέσσερις μηχανισμοί που έχουμε ορίσει, δηλαδή (1) τα ΑΠΑ, (2) τα ΜΠΑ, (3) τα ΜΠα-ε, και (4) οι Κ.Ε., είναι ισοδύναμοι μεταξύ-τους.

Προς το σκοπό αυτόν πρώτα θα κάνουμε τη σύνδεση μεταξύ των Κ.Ε. και των ΜΠΑ-ε.

Θεώρημα 2.6.1: Για κάθε Κ.Ε. υπάρχει ένα ΜΠΑ-ε που απόδέχεται τη γλώσσα L που παράγει η Κ.Ε.

Άσκηση 2.6.1: Κάνοντας χρήση της απόδειξης του θεωρήματος αυτού, κατασκευάστε ένα ΜΠΑ-ε για την Κ.Ε. (0 + 01)^*. Μην απλοποιήσετε καμιά ακμή ή σύνολο καταστάσεων του προκύπτοντος γράφου.

Ας ανακεφαλαιώσουμε τα συμπεράσματα που έχουμε συνάγει και αποδείξει έως τώρα.

Εικ. 2.6.1

Η παραπάνω εικόνα απεικονίζει τις σχέσεις μεταξύ των διαφόρων “μηχανών” (αυτομάτων και κανονικών εκφράσεων) που έχουμε βρει μέχρι τώρα. Το βέλος από το είδος μηχανής Χ στο είδος μηχανής Ψ πρέπει να ερμηνευτεί ως: «Χ → Ψ: δοσμένης μιας μηχανής τύπου Ψ, μπορούμε να κατασκευάσουμε μηχανή τύπου Χ που να αποδέχεται την ίδια γλώσσα όπως η Ψ.» Για παράδειγμα, το θεώρημα 2.6.1, παραπάνω, μας λέει οτι δοσμένης μιας μηχανής τύπου κανονικών εκφράσεων μπορούμε να κατασκευάσουμε μηχανή τύπου ΜΠΑ-ε που να αποδέχεται την ίδια γλώσσα.

Το βέλος από τις Κ.Ε. στα ΑΠΑ στην εικ. 2.6.1 σημειώνεται διακεκομμένο γιατί δεν έχουμε αποδείξει ακόμα οτι δοσμένου ενός ΑΠΑ μπορούμε να κατασκευάσουμε μια Κ.Ε. που να παράγει τη γλώσσα που αποδέχεται το ΑΠΑ· πράγμα που πρόκειται να αποδείξουμε ευθύς αμέσως.

Θεώρημα 2.6.2: Αν η γλώσσα L γίνεται αποδεκτή από ένα ΑΠΑ, τότε υπάρχει  μια Κ.Ε. που παράγει την L.

Απόδειξη. Έστω οτι η L γίνεται αποδεκτή από το ΑΠΑ Μ με n καταστάσεις, που τις απαριθμούμε από το 1 ως το n: Μ = ({q1, ..., qn}, Σ, δ, q1, F) Θα συμβολίσουμε με   το σύνολο όλων των συμβολοσειρών x που πηγαίνουν το αυτόματο από την κατάσταση qi σε κατάσταση qj, χωρίς να περάσει από κάποια κατάσταση με αύξοντα αριθμό μεγαλύτερο του k. Μέσω τύπων, μπορούμε να το εκφράσουμε αυτό ως εξής: δ(qi, x) = qj, και για κάθε συμβολοσειρά y ε που είναι γνήσιο πρόθεμα του x και τέτοιο ώστε δ(qi, y) = ql, ισχύει οτι l k. Ας σημειωθεί οτι η έκφραση «να περάσει από κάποια κατάσταση» σημαίνει τόσο την είσοδο όσο και την έξοδο από αυτή την κατάσταση. Επίσης σημειώνουμε οτι τα i και j μπορούν να είναι μεγαλύτερα από το k. Εφόσον η κατάσταση με μέγιστο αύξοντα αριθμό είναι η qn, έπεται οτι το   περιλαμβάνει όλες τις συμβολοσειρές που μεταφέρουν το αυτόματο από την qi στην qj.       Μπορούμε επομένως να ορίσουμε το  αναδρομικά:       = {a | δ(q, a) = qj} αν i j, {a | δ(q, a) = qj} {ε} αν i = j =  ( ) *           Διαισθητικά, ο παραπάνω ορισμός του  σημαίνει οτι οι είσοδοι που κάνουν το Μ να μεταφερθεί από την qi στην qj χωρίς να περάσει από κατάσταση μεγαλύτερη (με μεγαλύτερο αύξοντα αριθμό) από την qk είναι:   • είτε στο (δηλ. ποτέ δεν περνούν από κατάσταση με αριθμό τόσο μεγάλο όσο το k), • είτε αποτελούνται από μια συμβολοσειρά στο    (που μεταφέρει το Μ στην qk για πρώτη φορά), ακολουθούμενες από μηδέν ή περισσότερες συμβολοσειρές στο    (που μεταφέρουν το Μ από την qk πίσω στην qk χωρίς να περάσει από την qk ή κάποια άλλη κατάσταση με μεγαλύτερο αύξοντα αριθμό), ακολουθούμενες από συμβολοσειρά στο    (που μεταφέρει το Μ από την qk στην qj).           Πρέπει να δείξουμε οτι i, j, k υπάρχει μια κανονική έκφραση   που παράγει τη γλώσσα . Θα το κάνουμε μέσω επαγωγής στο k.           Επαγωγική βάση (k = 0): το  είναι ένα πεπερασμένο σύνολο συμβολοσειρών, καθεμία από τις οποίες είναι είτε το ε, είτε ένα απλό σύμβολο. Επομένως η   μπορεί να γραφεί: a1 + a2 + ... + ap (ή a1 + a2 + ... + ap + ε αν i = j), όπου {a1, a2, ..., ap} είναι το σύνολο όλων των συμβόλων a έτσι ώστε δ(qi, a) = qj. Αν δεν υπάρχουν τέτοια a, τότε η   αντιστοιχεί στο (ή στο ε στην περίπτωση i = j).   Επαγωγικό βήμα:ο αναδρομικός ορισμός για το     που δόθηκε παραπάνω προφανώς περιλαμβάνει μόνο πράξεις επί κανονικών εκφράσεων: την ένωση, τη συνένωση, και την κλειστότητα. Από την επαγωγική υπόθεση, για κάθε l και m υπάρχει μια κανονική έκφραση    τέτοια ώστε L( ) = . Άρα για το    μπορούμε να επιλέξουμε την κανονική έκφραση:   ( )( )*( ) +   ,   πράγμα που ολοκληρώνει την επαγωγή. Για να ολοκληρώσουμε και την απόδειξη, πρέπει μόνο να παρατηρήσουμε οτι: εφόσον το     συμβολίζει τις ετικέτες όλων των διαδρομών από την q1 στην qj. Επομένως η L(Μ) αντιπροσωπεύεται από την κανονική έκφραση: όπου   . ▓

Με το παραπάνω θεώρημα, το διακεκομμένο βέλος της εικ. 2.6.1 μπορεί να μετατραπεί σε συνεχές.

Επειδή όμως δημιουργείται έτσι ένας κύκλος, έχουμε ουσιαστικά αποδείξει την ισοδυναμία των τεσσάρων αυτών ειδών μηχανών· γιατί, για να αποδείξουμε, για παράδειγμα, οτι κάθε Κ.Ε. μπορεί να παρασταθεί από ένα ΜΠΑ-ε, αρκεί να κάνουμε τον κύκλο, περνώντας από τις Κ.Ε. στα ΑΠΑ, στη συνέχεια στα ΜΠΑ, και τέλος στα ΜΠΑ-ε. Επομένως μπορούμε το όλο συμπέρασμα περί ισοδυναμίας να το παραστήσουμε με την εικόνα που ακολουθεί, όπου τα βέλη έχουν αντικατασταθεί από απλές ακμές ενός μη κατευθυνόμενου γράφου:

Εικ. 2.6.2

2.7 Άλλα είδη πεπερασμένων αυτομάτων

Τα ΑΠΑ, ΜΠΑ, ΜΠΑ-ε, και οι Κ.Ε. δεν είναι τα μόνα είδη αυτομάτων με υπολογιστικές δυνατότητες που είναι τελικά ισοδύναμες μεταξύ-τους. Υπάρχουν και άλλα είδη, όλα ισοδύναμα με τα παραπάνω. Μερικά από αυτά θα αναφερθούν με συντομία εδώ, χωρίς όμως αποδείξεις θεωρημάτων σχετικά με την ισοδυναμία-τους με τα ΑΠΑ, την οποία ο αναγνώστης θα πρέπει να θεωρήσει δεδομένη.

2.7.1 Πεπερασμένα αυτόματα διπλής κατεύθυνσης

Μέχρι τώρα, η συμβολοσειρά της εισόδου διαβαζόταν προς τη μία κατεύθυνση· ας πούμε, “από τα αριστερά προς τα δεξιά”, αν και αυτό εξαρτάται από το γεγονός οτι στην ελληνική (και σε άλλα “δυτικά” συστήματα γραφής) γράφουμε από τα αριστερά προς τα δεξιά. Η ουσιαστική παρατήρηση είναι οτι άπαξ και ένα σύμβολο εισόδου ιδωθεί από το αυτόματο και γίνει η επεξεργασία-του, το σύμβολο αυτό “χάνεται”, και το αυτόματο δεν ασχολείται πλέον με αυτό.

Είναι δυνατό να θεωρήσουμε αυτόματα “διπλής κατεύθυνσης”, όπου δηλαδή μια υποτιθέμενη “κεφαλή” που διαβάζει την είσοδο δεν κινείται μόνο προς μία κατεύθυνση (“από τα αριστερά προς τα δεξιά”), αλλά μπορεί να κινηθεί και προς την άλλη (“από τα δεξιά προς τα αριστερά”), ξαναδιαβάζοντας κάποια σύμβολα εισόδου που ήδη απασχόλησαν το αυτόματο. Έτσι, στην απεικόνιση δ, τις εντολές του τύπου «όντας στην κατάσταση q_i και με σύμβολο εισόδου το a, πήγαινε στην κατάσταση q_j» πρέπει να τις αντικαταστήσουμε με εντολές του τύπου: «όντας στην κατάσταση q_i και με σύμβολο εισόδου το a, πήγαινε στην κατάσταση q_j και μετακίνησε την κεφαλή ανάγνωσης της εισόδου κατά μία θέση [Αριστερά ή Δεξιά]». Δεν είναι καθόλου δύσκολο να κωδικοποιήσουμε με ένα μαθηματικό ορισμό αυτή την ιδέα:

Ορισμός: Ένα αιτιοκρατικό πεπερασμένο αυτόματο διπλής κατεύθυνσης (ΑΠΑ-2) είναι μια πεντάδα (Q, Σ, δ, q₀, F), της οποίας όλα τα στοιχεία είναι όπως και στα ΑΠΑ, με εξαίρεση τη δ, η οποία τώρα είναι απεικόνιση από το Q X Σ στο Q X {Δ, Α}. Όταν δ(q_i, a) = (q_j, Δ), τότε το αυτόματο συμπεριφέρεται όπως και ένα απλό ΑΠΑ, δηλαδή: με σύμβολο το a στην είσοδο μεταφέρεται από την κατάσταση q_i στην κατάσταση q_j, και ετοιμάζεται να δεχτεί το επόμενο σύμβολο εισόδου (“Δεξιά”). Όταν όμως δ(q_i, a) = (q_j, Α), τότε το αυτόματο κάνει μεν το ίδιο ως προς το a και τις δύο καταστάσεις, αλλά αφού βρεθεί στην κατάσταση q_j ετοιμάζεται να διαβάσει το σύμβολο που βρίσκεται πριν από το a στην είσοδο (“Αριστερά”). Αν δεν υπάρχει τέτοιο σύμβολο (που συμβαίνει στην αρχή της συμβολοσειράς εισόδου), τότε η δ εκεί δεν ορίζεται, και το αυτόματο απορρίπτει (δεν αποδέχεται) την είσοδο που του δόθηκε.

Το ΑΠΑ-2 αποδέχεται την είσοδό του αν βρεθεί σε τελική κατάσταση, και ταυτόχρονα έχει εξαντλήσει όλα τα σύμβολα εισόδου, δηλαδή η νοητή “κεφαλή” του ΑΠΑ-2 βρίσκεται “δεξιά” του τελευταίου συμβόλου εισόδου.

Εικ. 2.7.1: Σχηματική παράσταση “ταινίας εισόδου” και “κεφαλής” ενός ΑΠΑ-2.

Στην εικόνα 2.7.1 δίνεται μια σχηματική παράσταση εννοιών που δεν είναι απαραίτητες για τον ορισμό των ΑΠΑ-2, μας βοηθούν όμως στην κατανόηση των αυτομάτων, και καλό είναι να τις έχουμε υπόψη από εδώ και στο εξής. Θεωρούμε οτι η είσοδος είναι τοποθετημένη σε μια “ταινία”, την οποία “διαβάζει” το αυτόματο, ενώ υπάρχει και μια “κεφαλή” που μπορεί να μετακινηθεί αριστερά ή δεξιά στην ταινία. Η κεφαλή είναι τοποθετημένη πάντα μεταξύ των συμβόλων εισόδου, και στο επόμενο (χρονικά) “βήμα” διαβάζει και επεξεργάζεται (σύμφωνα με τη δ) το σύμβολο στα δεξιά-της, αν αυτό υπάρχει· διαβάζοντάς το όμως δεν μετακινείται παρά μόνο αν η δ της ορίσει να μετακινηθεί κατά μία θέση αριστερά ή δεξιά.

Καμία από τις παραπάνω έννοιες δεν χρειαζόταν να αναφερθεί στα άλλα αυτόματα που γνωρίσαμε μέχρι στιγμής, γιατί η “κεφαλή” μετακινείτο μόνο προς μία κατεύθυνση, και υποχρεωτικά μετά από την ανάγνωση του επόμενου συμβόλου εισόδου.

Άσκηση 2.7.1: Κατασκευάστε ένα ΑΠΑ-2 που να αποδέχεται τη γλώσσα που αποτελείται από συμβολοσειρές από το Σ = {a, b} με την εξής ιδιότητα: πριν από κάθε ακολουθία της μορφής bba υπάρχουν δέκα συνεχόμενα a. Σκεφτήτε τώρα πώς θα φτιάχνατε ένα απλό ΑΠΑ που να αποδέχεται την ίδια γλώσσα, και παρατηρήστε πώς το ΑΠΑ-2 απλοποιεί τη δομή αυτού του ΑΠΑ.

Μπορεί να αποδειχτεί οτι τα ΑΠΑ-2 αποδέχονται και αυτά τις κανονικές γλώσσες, επομένως είναι ισοδύναμα με τα άλλα τέσσερα μέλη της οικογένειας αυτομάτων που εξετάσαμε μέχρι στιγμής. Η απόδειξη είναι αρκετά περίπλοκη και υπερβαίνει το εύρος και τον σκοπό του παρόντος μαθήματος· ο αναγνώστης που ενδιαφέρεται γι’ αυτή μπορεί να συμβουλευτεί τη βιβλιογραφία στο [1]. Βεβαιωθήτε όμως οτι αντιλαμβάνεστε πώς ένα ΑΠΑ-2 μπορεί να προσομοιώσει ένα ΑΠΑ.

Επίσης, μπορούμε να ορίσουμε τα μη-αιτιοκρατικά αυτόματα διπλής κατεύθυνσης (ΜΠΑ-2), σε πλήρη αναλογία με τα ΜΠΑ και ΑΠΑ-2. Αποδεικνύεται οτι ούτε τα ΜΠΑ-2 προσθέτουν κάτι το καινούργιο, αλλά αποδέχονται κι αυτά τις κανονικές γλώσσες.

Επίσης, άλλη επέκταση στον ορισμό των αυτομάτων είναι να επιτρέπουμε στην “κεφαλή” να μην κινείται ούτε δεξιά ούτε αριστερά, αλλά να παραμένει ακίνητη δοσμένου ενός συμβόλου και όντας σε μια κατάσταση. Αποδεικνύεται οτι ούτε μ’ αυτή την προσθήκη επεκτείνουμε τις αποδεκτές γλώσσες πέρα από τις κανονικές.

2.7.2 Μηχανές Μουρ

Μια άλλη ιδέα που μπορούμε να προσθέσουμε στα μέχρι στιγμής αυτόματα είναι να παράγουν και κάποια σύμβολα εξόδου (κάτι ανάλογο με τον εκτυπωτή ενός υπολογιστή, ή με την οθόνη-του). Όλα τα αυτόματα που είδαμε μέχρι στιγμής απλώς διαβάζουν την είσοδό τους, και αν πρόκειται να απαντήσουν (να “εκτυπώσουν”) κάτι, αυτό είναι της μορφής: “απόρριψη” ή “αποδοχή”· δηλαδή είναι σαν να δίνουν σε μια “έξοδο” ένα μόνο δυαδικό ψηφίο πληροφορίας: το 0 ή το 1.

Η Μηχανή Μουρ (Moore) ορίζεται έτσι ώστε να μπορεί να συσχετίσει και ένα σύμβολο εξόδου με κάθε κατάστασή της, παρμένο από ένα αλφάβητο εξόδου. Συγκεκριμένα:

Ορισμός: Μια Μηχανή Μουρ είναι μια εξάδα (Q, Σ, Δ, δ, λ, q₀), όπου τα Q, Σ, δ, και q₀ είναι όπως και στα ΑΠΑ. Το Δ είναι ένα σύνολο συμβόλων που ονομάζεται αλφάβητο εξόδου. Και το λ είναι μια απεικόνιση από το Q στο Δ που συσχετίζει ένα σύμβολο εξόδου με κάθε κατάσταση.

Συνεπώς η έξοδος μιας Μηχανής Μουρ δεδομένης μιας συμβολοσειράς a₁a₂...a_n, n 0, είναι η ακολουθία λ(q₀)λ(q₁)...λ(q_n), όπου q₀, q₁, ..., q_n είναι η ακολουθία καταστάσεων έτσι ώστε δ(q_i–1, a_i) = q_i 1 i n.

Προφανώς η Μηχανή Μουρ δίνει ως έξοδο το λ(q₀) σαν απάντηση στο ε.

Βλέπουμε επίσης οτι η Μηχανή Μουρ δεν έχει τελική κατάσταση (ή καταστάσεις). Δεν χρειάζεται, γιατί τώρα η έννοια της αποδοχής ή απόρριψης έχει γενικευτεί, οπότε από το 0/1 έχει γίνει οποιαδήποτε συμβολοσειρά από το αλφάβητο εξόδου.

Άσκηση 2.7.2: Δείξτε με ποιον τρόπο οποιοδήποτε ΑΠΑ μπορεί να προσομοιωθεί από μια Μηχανή Μουρ· δηλαδή, δοσμένου ενός ΑΠΑ, κατασκευάστε μια Μηχανή Μουρ που να κάνει ότι και το ΑΠΑ.

2.7.3 Μηχανές Μήλυ

Αντί να παράγει σύμβολο εξόδου ανά κατάσταση, ένα αυτόματο θα μπορούσε να παράγει σύμβολο εξόδου ανά μετάβαση, δηλαδή ανά ακμή του γράφου-του. Αυτό ακριβώς κάνει μια Μηχανή Μήλυ (Mealy).

Ορισμός: Μια Μηχανή Μήλυ είναι μια εξάδα (Q, Σ, Δ, δ, λ, q₀), όπου όλα τα στοιχεία-της είναι όπως στη Μηχανή Μουρ, εκτός από το λ, που τώρα απεικονίζει το Q X Σ στο Δ· ήτοι το λ(q, a) δίνει το σύμβολο εξόδου που αντιστοιχεί στη μετάβαση από την κατάσταση q δεδομένου του συμβόλου εισόδου a.

Συνεπώς η έξοδος μιας Μηχανής Μήλυ δεδομένης μιας συμβολοσειράς a₁a₂...a_n, n 0, είναι η ακολουθία λ(q₀, a₁)λ(q₁, a₂)...λ(q_n–1, a_n), όπου q₀, q₁, ..., q_n είναι η ακολουθία καταστάσεων έτσι ώστε δ(q_i–1, a_i) = q_i 1 i n. Η ακολουθία αυτή έχει μήκος n, και όχι n + 1 όπως στη Μηχανή Μουρ.

Προφανώς η Μηχανή Μήλυ δίνει ως έξοδο το ε σαν απάντηση στο ε.

Άσκηση 2.7.3: Δείξτε με ποιον τρόπο οποιαδήποτε Μηχανή Μουρ μπορεί να προσομοιωθεί από μια Μηχανή Μήλυ· δηλαδή, δοσμένης μιας Μηχανής Μουρ, κατασκευάστε μια Μηχανή Μήλυ που να κάνει ότι και η Μηχανή Μουρ.

2.8 Ιδιότητες κλειστότητας κανονικών γλωσσών

Ένα χαρακτηριστικό των κανονικών γλωσσών είναι οτι υπάρχουν αλγόριθμοι για να απαντηθούν διάφορα ερωτήματα που τις αφορούν (πράγμα που θα δούμε οτι δεν ισχύει σε γλώσσες με μεγαλύτερες δυνατότητες). Για παράδειγμα: είναι η γλώσσα που παράγει ένα αυτόματο πεπερασμένη; Είναι κενή; Είναι το συμπλήρωμά της στο δοσμένο αλφάβητο κανονική γλώσσα; Αυτά και διάφορα άλλα ερωτήματα θα εξετάσουμε στη συνέχεια. Φυσικά, όταν βγάζουμε συμπεράσματα για κανονικές γλώσσες, ο αναγνώστης θα πρέπει να έχει κατά νου οτι τα ίδια συμπεράσματα βγάζουμε για όλα τα πεπερασμένα αυτόματα που έχουμε εξετάσει μέχρι στιγμής, εφόσον έχουμε αποδείξει (ή υποδείξει) την ισοδυναμία-τους.

Θεώρημα 2.8.1: Οι κανονικές γλώσσες είναι κλειστές ως προς την ένωση, τη συνένωση, και την κλειστότητα Κλέινι.

Θυμίζουμε οτι κάθε γλώσσα είναι απλώς ένα σύνολο συμβολοσειρών από ένα αλφάβητο Σ. Επομένως το συμπλήρωμα L΄ μιας γλώσσας L είναι όλες οι συμβολοσειρές του Σ^* – L.

Θεώρημα 2.8.2: Οι κανονικές γλώσσες είναι κλειστές ως προς την πράξη συμπλήρωμα.

Το παραπάνω θεώρημα μας επιτρέπει να συμπεράνουμε την κλειστότητα για μια ακόμη πράξη συνόλων:

Θεώρημα 2.8.3: Οι κανονικές γλώσσες είναι κλειστές ως προς την πράξη της τομής.

2.9 Αποφασίσιμα προβλήματα

Στην προηγούμενη υποενότητα συναντήσαμε διάφορα προβλήματα για τα οποία υπάρχει μια πλήρης απάντηση. Για παράδειγμα, για το πρόβλημα: «Να κατασκευαστεί αυτόματο που να αποδέχεται το συμπλήρωμα μιας κανονικής γλώσσας», υπάρχει πλήρης απάντηση που δίνεται από την απόδειξη του θεωρήματος 2.8.2. Τα προβλήματα αυτά ονομάζονται αποφασίσιμα.

Ορισμός: Ένα πρόβλημα λέγεται αποφασίσιμο όταν υπάρχει αποτελεσματική μέθοδος η οποία δίνει λύση στο πρόβλημα αυτό.

Ορισμός: Μια μέθοδος για τη λύση ενός προβλήματος λέγεται αποτελεσματική όταν δίνει πάντοτε απάντηση (λύση) για οποιαδήποτε είσοδο δεδομένων του προβλήματος.

Παράδειγμα: Η εύρεση του μέγιστου κοινού διαιρέτη δύο ακεραίων είναι αποφασίσιμο πρόβλημα, γιατί υπάρχει αποτελεσματική μέθοδος που το λύνει: ο γνωστός “Ευκλείδειος αλγόριθμος”.

Στο παραπάνω παράδειγμα αναφέρθηκε η λέξη “αλγόριθμος” εντελώς περιστασιακά, χωρίς ορισμό. Αυτό δεν γίνεται χωρίς λόγο. Μέχρι σήμερα δεν υπάρχει πλήρης συμφωνία για το ποιες μέθοδοι πρέπει να ονομάζονται “αλγόριθμοι”. Εμείς θα ακολουθήσουμε την “κλασική” σχολή των Turing, Church, Kleene, και Gödel, σύμφωνα με την οποία ένας αλγόριθμος είναι οτιδήποτε μπορεί να εκτελεστεί από μια Μηχανή Τούρινγκ (Turing), μηχανή που θα γνωρίσουμε σε ένα από τα επόμενα κεφάλαια. Κατά την αντίληψη αυτή, ένας αλγόριθμος είναι κάτι παραπάνω (υπολογιστικά πιο ισχυρό) από μια αποτελεσματική μέθοδο.

Ορισμός: Τις αποτελεσματικές μεθόδους θα τις ονομάζουμε και πλήρεις αλγορίθμους.

Όρισμός: Μία μέθοδος που δίνει απαντήσεις σε ένα γνήσιο υποσύνολο όλων των δυνατών δεδομένων εισόδου-της, ενώ στα υπόλοιπα δεδομένα εισόδου δεν δίνει απάντηση (π.χ. συνεχίζει να υπολογίζει επ’ άπειρο) ονομάζεται ημιαποφασίσιμη, ή αλλιώς, ημιαλγόριθμος, και τα αντίστοιχα προβλήματα λέγονται ημιαποφασίσιμα.

Παράδειγμα: Το πρόβλημα της εύρεσης απόδειξης για οποιοδήποτε θεώρημα είναι ημιαποφασίσιμο. Υπάρχει δηλαδή ημιαλγόριθμος που έχει την εξής ιδιότητα: αν υπάρχει απόδειξη του θεωρήματος, δοσμένων των αξιωμάτων και των άλλων θεωρημάτων που έχουν ήδη αποδειχτεί, ο ημιαλγόριθμος αυτός θα βρει την απόδειξη και θα τη δώσει στην έξοδο· αν όμως δεν υπάρχει απόδειξη, τότε ο ημιαλγόριθμος θα συνεχίσει να δουλεύει επ’ άπειρο, ενώ ο παρατηρητής που περιμένει τη διαδικασία (το πρόγραμμα που υλοποιεί τον αλγόριθμο) να τελειώσει δεν γνωρίζει αν η διαδικασία θα τελειώσει κάποτε δίνοντας μια απόδειξη, ή αν θα συνεχίσει επ’ άπειρο. Αποδεικνύεται οτι δεν υπάρχει πλήρης αλγόριθμος που να λύνει το πρόβλημα της εύρεσης απόδειξης ενός θεωρήματος, αλλά μόνο ημιαλγόριθμος.

Θα αναβάλουμε τον ορισμό της έννοιας του γενικού αλγορίθμου μέχρι το κεφάλαιο των Μηχανών Τούρινγκ, όπου θα συναντήσουμε και τα αναποφασίσιμα προβλήματα, αυτά για τα οποία δεν υπάρχει αλγόριθμος που να τα λύνει.

Θεώρημα 2.9.1: Το πρόβλημα του αν η γλώσσα L που γίνεται αποδεκτή από το αυτόματο Μ είναι μη κενή, πεπερασμένη, ή άπειρη, είναι αποφασίσιμο.

Για να αποδείξουμε το θεώρημα 2.9.1 θα χρησιμοποιήσουμε δύο λήμματα, τα οποία και θα αποδείξουμε.

Λήμμα 2.9.1: Η γλώσσα L που γίνεται αποδεκτή από ένα αυτόματο Μ με n καταστάσεις είναι μη κενή τότε και μόνο τότε όταν το Μ αποδέχεται μια συμβολοσειρά μήκους l < n.

Λήμμα 2.9.2: Η γλώσσα L που γίνεται αποδεκτή από ένα αυτόματο Μ με n καταστάσεις είναι άπειρη τότε και μόνο τότε όταν το Μ αποδέχεται μια συμβολοσειρά μήκους l όπου n l.

Το θεώρημα 2.9.1 τώρα αποδεικνύεται με απλή χρήση των λημμάτων 2.9.1 και 2.9.2:

Παρατηρούμε οτι στην απόδειξη του θεωρήματος 2.9.1 έχουμε κατασκευές αυτομάτων, άρα αποτελεσματικές μεθόδους και πλήρεις αλγορίθμους που απαντούν τα ερωτήματα αυτά.

Θεώρημα 2.9.2: Το πρόβλημα του αν δύο αυτόματα Μ₁ και Μ₂ αποδέχονται την ίδια γλώσσα L είναι αποφασίσιμο.

Θεώρημα 2.9.3: Δοσμένου ενός αυτομάτου Μ, υπάρχει ένα άλλο αυτόματο Μ΄ που αποδέχεται την ίδια γλώσσα όπως το Μ, και έχει μικρότερο ή ίσο αριθμό καταστάσεων από το Μ.

Το παραπάνω θεώρημα μας λέει οτι μπορούμε πάντα να ελαχιστοποιήσουμε τον αριθμό των καταστάσεων ενός πεπερασμένου αυτομάτου.

3. Γραμματικές Χωρίς Συμφραζόμενα

3.1 Εισαγωγή στην έννοια της γραμματικής

Στην προηγούμενη ενότητα συναντήσαμε την έννοια του αυτομάτου. Στην παρούσα θα εξοικειωθούμε με την έννοια της γραμματικής. Αργότερα θα διαπιστώσουμε οτι υπάρχει πλήρης αντιστοιχία μεταξύ αυτομάτων και γραμματικών. Πάντως οι γραμματικές που θα εξετάσουμε στην παρούσα ενότητα θα είναι πιο ισχυρές σε υπολογιστική ικανότητα από τα αυτόματα που γνωρίσαμε. Ας δούμε όμως τί είναι μια γραμματική, μέσω ενός παραδείγματος από μια φυσική γλώσσα: την ελληνική.

Έστω οτι δίνονται οι παρακάτω κανόνες:

1. Πρόταση → ΟυσιαστικήΦράση ΡηματικήΦράση

2. ΟυσιαστικήΦράση → Άρθρο ΕπιθετικήΦράση

3. ΕπιθετικήΦράση → Επίθετο ΕπιθετικήΦράση

4. ΕπιθετικήΦράση → Ουσιαστικό

5. ΡηματικήΦράση → Ρήμα Επίρρημα

6. Άρθρο → το

7. Επίθετο → ανοιχτό

8. Επίθετο → μεγάλο

9. Ουσιαστικό → κουτί

10. Ουσιαστικό → παράθυρο

11. Ρήμα → έκλεισε

12. Ρήμα → χάλασε

13. Επίρρημα → εντελώς

14. Επίρρημα → θορυβωδώς

Κάθε κανόνας έχει ένα αριστερό και ένα δεξί μέλος, αριστερά και δεξιά του → αντιστοίχως. Όσες λέξεις αρχίζουν με κεφαλαίο γράμμα λέγονται “μεταβλητά σύμβολα”, ή απλώς “μεταβλητές”· ενώ όσες αρχίζουν με μικρό γράμμα λέγονται “τερματικά σύμβολα”, ή απλώς “τερματικά”. Κάθε μεταβλητή μπορεί να αντικατασταθεί μέσω ενός κανόνα που έχει αυτή τη μεταβλητή στο αριστερό-του μέλος, δηλαδή αριστερά από το →. Μας δίνεται επίσης η πληροφορία οτι η πρώτη από τις παραπάνω μεταβλητές (η “Πρόταση”) λέγεται “αρχική”.

Ξεκινάμε λοιπόν από την αρχική μεταβλητή:

(α) Πρόταση

Αυτή εμφανίζεται στον κανόνα 1:

1. Πρόταση → ΟυσιαστικήΦράση ΡηματικήΦράση

Αυτός ο κανόνας έχει δύο μεταβλητές: την ΟυσιαστικήΦράση και τη ΡηματικήΦράση, από τις οποίες μπορεί να αντικατασταθεί η Πρόταση. Επομένως η (α) γίνεται:

(β) ΟυσιαστικήΦράση ΡηματικήΦράση

Για την ΟυσιαστικήΦράση έχουμε τον κανόνα 2 όπου αυτή εμφανίζεται στο αριστερό μέλος:

2. ΟυσιαστικήΦράση → Άρθρο ΕπιθετικήΦράση

Αντκαθιστώντας μέσω αυτού του κανόνα την ΟυσιαστικήΦράση στη (β) παίρνουμε:

(γ) Άρθρο ΕπιθετικήΦράση ΡηματικήΦράση

Όσο για τη ΡηματικήΦράση, αυτή μπορούμε να την αντικαταστήσουμε μέσω του κανόνα 5:

5. ΡηματικήΦράση → Ρήμα Επίρρημα

Οπότε η (γ) γίνεται:

(δ) Άρθρο ΕπιθετικήΦράση Ρήμα Επίρρημα

Για το Άρθρο μας δίνεται μόνο μία επιλογή, μέσω του κανόνα 6, όπου το Άρθρο αντικαθίσταται από τερματικό σύμβολο:

(ε) το ΕπιθετικήΦράση Ρήμα Επίρρημα

Η ΕπιθετικήΦράση τώρα, αξίζει λίγο περισσότερη προσοχή, γιατί γι’ αυτήν έχουμε δύο κανόνες: τους 3 και 4, μέσω των οποίων μπορούμε να την αντικαταστήσουμε. Επιλέγουμε, αυθαίρετα, τον κανόνα 3:

3. ΕπιθετικήΦράση → Επίθετο ΕπιθετικήΦράση

οπότε η (ε) γίνεται:

(ϛ) το Επίθετο ΕπιθετικήΦράση Ρήμα Επίρρημα

Παραμένει δηλαδή η μεταβλητή ΕπιθετικήΦράση. Αν εφαρμόσουμε άλλη μια φορά τον κανόνα 3, παίρνουμε:

(ζ) το Επίθετο Επίθετο ΕπιθετικήΦράση Ρήμα Επίρρημα

Τώρα ας αντικαταστήσουμε την ΕπιθετικήΦράση μέσω του κανόνα 4:

4. ΕπιθετικήΦράση → Ουσιαστικό

Οπότε η (ζ) γίνεται:

(η) το Επίθετο Επίθετο Ουσιαστικό Ρήμα Επίρρημα

Τώρα έμειναν για αντικαταστάσεις μεταβλητών μόνο κανόνες που οδηγούν σε τερματικά σύμβολα. Αν κάνουμε ταυτόχρονη εφαρμογή των κανόνων 7, 8, 10, 11, 14 στην (η), παίρνουμε:

(θ) το ανοιχτό μεγάλο παράθυρο έκλεισε θορυβωδώς

η οποία είναι μια πιθανή πρόταση της ελληνικής γλώσσας.

Οι κανόνες αυτοί λέγονται συντακτικοί ή γραμματικοί κανόνες, και το σύστημα των 14 κανόνων συντακτικό ή γραμματική.

Στο παραπάνω παράδειγμα επιλέγαμε αυθαίρετα κανόνες προς εφαρμογή, με αποτέλεσμα να παραγάγουμε μια πρόταση (συμβολοσειρά, της οποίας όμως κάθε σύμβολο αντιστοιχεί σε ολόκληρη λέξη). Κάνοντας διαφορετική (αλλά πάντα αυθαίρετη) εφαρμογή κανόνων, θα μπορούσαμε να παραγάγουμε τις προτάσεις:

• το παράθυρο χάλασε εντελώς

• το μεγάλο ανοιχτό κουτί έκλεισε εντελώς

• το μεγάλο μεγάλο μεγάλο ανοιχτό μεγάλο ανοιχτό κουτί χάλασε θορυβωδώς

Η τρίτη περίπτωση μας δείχνει οτι η γραμματική αυτή δημιουργεί και προτάσεις που δεν έχουν νόημα στην ελληνική γλώσσα. Λέμε όμως οτι είναι “συντακτικά σωστές”, εφόσον παρήχθησαν εφαρμόζοντας τους κανόνες από το δοσμένο σύνολο συντακτικών κανόνων.

Άσκηση 3.1.1: Τροποποιήστε τη γραμματική αυτή, περιορίζοντας και/ή αναδιατυπώνοντας τους κανόνες-της, ώστε να μην είναι δυνατό να παραχθούν απεριόριστα μεγάλες συμβολοσειρές όπως εκείνη της 3ης περίπτωσης, παραπάνω. Ποιος κανόνας είναι υπεύθυνος για τις απεριόριστες συμβολοσειρές;

Προς το παρόν, μέσω της παραπάνω γραμματικής δεν έχουμε πετύχει κάτι σπουδαίο, γιατί οι προτάσεις που παράγονται από τη γραμματική αυτή θα μπορούσαν να περιγραφούν επαρκώς και από μια Κανονική Έκφραση (Κ.Ε.).

Άσκηση 3.1.2: Γράψτε την Κ.Ε. που παράγει ακριβώς τις προτάσεις (συμβολοσειρές) που παράγει και η ανωτέρω γραμματική.

Τώρα όμως θα δούμε μια γραμματική η οποία παράγει προτάσεις (συμβολοσειρές) που είναι αδύνατο να παρασταθούν από οποιαδήποτε Κ.Ε. Πρόκειται για τη γραμματική των αριθμητικών εκφράσεων, ή έστω κάποιου υποσυνόλου αυτών:

1. Έκφραση → Όρος + Όρος | Όρος – Όρος | Όρος

2. Όρος → Παράγοντας * Παράγοντας | Παράγοντας / Παράγοντας | Παράγοντας

3. Παράγοντας → ( Έκφραση ) | Έκφραση

4. Έκφραση → Μεταβλητή | ΦυσικόςΑριθμός

5. Μεταβλητή → x | y | z

6. ΦυσικόςΑριθμός → Ψηφίο_0 | Ψηφίο19 Ψηφία

7. Ψηφία → Ψηφίο_0 Ψηφία | Ψηφίο19 Ψηφία | Ψηφίο_0 | Ψηφίο19

8. Ψηφίο19 → 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

9. Ψηφίο_0 → 0

Αρχική μεταβλητή είναι η “Έκφραση”. Τα τερματικά σύμβολα σημειώνονται εδώ με κόκκινο χρώμα ώστε να ξεχωρίζουν από τα “συντακτικά σύμβολα” → και | . Πρέπει να παρατηρήσουμε εδώ οτι κάναμε χρήση του συμβόλου | (που το διαβάζουμε «είτε») ως συντομογραφία: Αντί να γράφουμε, π.χ.:

1. Α → α

2. Α → β

γράφουμε για συντομία:

1. Α → α | β

Κάτι άλλο που παρατηρούμε είναι οτι ένας κανόνας μπορεί να περιλαμβάνει μεταβλητές και τερματικά στο δεξί μέλος-του, σε οποιαδήποτε σειρά (σε αντίθεση με το πρώτο παράδειγμα όπου είχαμε διαχωρίσει μεταβλητές από τερματικά χάριν απλότητας).

Εύκολα βλέπουμε οτι η παραπάνω γραμματική, ξεκινώντας από την “Έκφραση”, παράγει συμβολοσειρές όπως οι ακόλουθες:

• 5 + 82

• 0 * x + (2 / 0)

• ((y – 1) / ((z) / 99))

• (((((0)))))

Και πάλι, μέσω του παραπάνω παραδείγματος, βλέπουμε οτι άλλη έννοια είναι η “συντακτικά σωστή έκφραση”, και άλλη η “χρήσιμη έκφραση” (ή αλλιώς: “έκφραση που έχει νόημα”). Π.χ. η έκφραση (((((0))))) είναι μεν συντακτικά σωστή, εφόσον παράγεται από τη γραμματική του παραδείγματος, αλλά “δεν έχει νόημα”, αφού ποτέ δεν θα χρησιμοποιούσαμε μια τέτοια έκφραση στην πράξη.

Αυτό που διαθέτουν αυτές οι συμβολοσειρές, και που δεν μπορούμε να το παραγάγουμε μέσω Κ.Ε., είναι οτι έχουν πάντα “ζυγισμένες παρενθέσεις”· δηλαδή για κάθε αριστερή παρένθεση “(” υπάρχει μια δεξιά παρένθεση “)” που της αντιστοιχεί. Και αυτή η ικανότητα, το “ζύγισμα” των συμβόλων, όπως θα δούμε, είναι η ουσιαστική ικανότητα που διακρίνει τις “γραμματικές χωρίς συμφραζόμενα” (που θα ορίσουμε αμέσως) από όλα τα αυτόματα και τις Κ.Ε. που γνωρίσαμε μέχρι τώρα.

Άσκηση 3.1.3: Σκεφτήτε ένα παράδειγμα διαδοχικών φράσεων από την ελληνική γλώσσα (όχι απαραίτητα πλήρων προτάσεων με ρήμα, χωρίς αυτό να απαγορεύεται) οι οποίες να δείχνουν οτι το παραπάνω “ζύγισμα συμβόλων” υπάρχει και στη φυσική γλώσσα. Όπως δηλαδή, μέσω του προηγούμενου παραδείγματος θα παίρναμε διαδοχικές συμβολοσειρές όπως: (1), ((1)), (((1))), κλπ., σκεφτήτε ένα ανάλογο παράδειγμα και με φράσεις της ελληνικής — χωρίς να δώσετε τη γραμματική με τους κανόνες-της, αλλά μόνο τις παραγόμενες διαδοχικές φράσεις ή προτάσεις.

Το “ζύγισμα” των συμβόλων είναι μια απαραίτητη ιδιότητα στο συντακτικό των γλωσσών προγραμματισμού. Π.χ. στις C, C++, και Java, οι εντολές προγράμματος κλείνονται μεταξύ ζευγών “{” και “}”· στην Pascal και σε απογόνους-της, κλείνονται μεταξύ ζευγών “begin” και “end”· στη Lisp και στους απογόνους-της, μεταξύ ζευγών “(” και “)”· κλπ.

3.2 Ορισμοί βασικών εννοιών

Ερχόμαστε τώρα στον ορισμό της έννοιας της γραμματικής χωρίς συμφραζόμενα.

Ορισμός: Μια γραμματική χωρίς συμφραζόμενα (ΓΧΣ) είναι μια τετράδα G = (V, T, P, S), όπου το V είναι ένα πεπερασμένο σύνολο συμβόλων που θα ονομάζουμε μεταβλητές, το T είναι πεπερασμένο σύνολο συμβόλων που θα ονομάζουμε τερματικά, το P είναι ένα πεπερασμένο σύνολο συντακτικών κανόνων, όπου κάθε συντακτικός κανόνας είναι της μορφής Α → α, όπου το Α είναι μεταβλητή, και το α είναι συμβολοσειρά από το (V T)^*, δηλαδή οποιαδήποτε ακολουθία (μπορεί και κενή) μεταβλητών ή τερματικών, και τέλος το S V είναι μία συγκεκριμένη μεταβλητή που ονομάζεται αρχικό σύμβολο.

Τις γραμματικές αυτές τις λέμε “χωρίς συμφραζόμενα” γιατί οι κανόνες-τους είναι της μορφής Α → α, δηλαδή το αριστερό μέλος κάθε κανόνα είναι μια απλή μεταβλητή, “χωρίς συμφραζόμενα”. Σε επόμενη ενότητα του παρόντος μαθήματος θα γνωρίσουμε και γραμματικές με κανόνες της μορφής βΑγ → α, όπου τα β και γ είναι τα “συμφραζόμενα” του Α· δηλαδή για να εφαρμοστεί ο κανόνας αυτός θα πρέπει το Α να βρίσκεται “εντός των συμφραζομένων” β και γ. Καθώς δεν επιτρέπουμε τέτοιους κανόνες προς το παρόν, ονομάζουμε τις γραμματικές που δίνονται από τον προηγούμενο ορισμό “χωρίς συμφραζόμενα” (και για συντομία: “ΓΧΣ”).

Θα χρησιμοποιούμε τους συμβολισμούς των οποίων κάναμε χρήση και στην εισαγωγική παράγραφο· δηλαδή το σύμβολο | για τη σύμπτυξη κανόνων, κεφαλαία γράμματα για τις μεταβλητές, μικρά (πεζά) για τα τερματικά, κλπ.

Ορισμός: Αν G = (V, T, P, S) είναι μια ΓΧΣ, το Α → α είναι ένας από τους κανόνες του P, και τα β και γ είναι συμβολοσειρές από το (V T)^*, τότε λέμε οτι ο κανόνας Α → α εφαρμόζει στη συμβολοσειρά βΑγ και παράγει το βαγ. Η εφαρμογή του κανόνα Α → α θα λέγεται παραγωγή (αγγλ.: derivation), και θα συμβολίζεται έτσι: βΑγ βαγ. Το συμβολισμό αυτό θα τον διαβάζουμε ως εξής: «το βΑγ παράγει απευθείας το βαγ.» (Θα δούμε αμέσως τί σημαίνει να παράγεται κάποια συμβολοσειρά αλλά όχι απευθείας.)

Έτσι, σε μια γραμματική G, δύο συμβολοσειρές σχετίζονται με τη σχέση όταν η μία παράγει απευθείας την άλλη.

Ορισμός: Έστω και πάλι η G όπως και προηγουμένως. Ας υποθέσουμε τώρα οτι τα α₁, α₂, ... , α_n είναι συμβολοσειρές από το (V T)^*, όπου n 1, και οτι:

α₁ α₂ ...  α_n–1 α_n.

Τότε λέμε οτι το α₁ παράγει το α_n στη γραμματική G (όχι κατανάγκη απευθείας, όπως στον προηγούμενο ορισμό). Την παραγωγή αυτή θα τη συμβολίζουμε έτσι: α₁ α_n.

Με άλλα λόγια, μπορούμε να πούμε οτι η σχέση είναι η ανακλαστική και μεταβατική κλειστότητα της σχέσης . Εναλλακτικά, α β τότε και μόνο τότε αν το β παράγεται από το α μέσω μηδέν ή περισσότερων παραγωγών του συνολου P της G.

Ορισμός: Η γλώσσα L(G) που παράγεται από τη γραμματική G = (V, T, P, S) είναι το σύνολο {w | w T^* και S w}.

Με άλλα λόγια, μια συμβολοσειρά ανήκει στην L(G) αν:

• η συμβολοσειρά αποτελείται αποκλειστικά από τερματικά σύμβολα, και

• η συμβολοσειρά μπορεί να παραχθεί από το S.

Ορισμός: γλώσσα χωρίς συμφραζόμενα ονομάζεται η γλώσσα L(G) που παράγεται από μια G που είναι ΓΧΣ.

Παράδειγμα: Έστω η G = (V, T, P, S), όπου V = {S, A, B}, T = {0, 1}, και το P είναι το εξής σύνολο κανόνων:

• S → 0Β | 1Α

• Α → 0 | 0S | 1ΑΑ

• Β → 1 | 1S | 0ΒΒ

Μπορεί να αποδειχτεί, μέσω επαγωγής στο μήκος της παραγόμενης συμβολοσειράς, οτι η γλώσσα χωρίς συμφραζόμενα L(G) είναι το σύνολο όλων των συμβολοσειρών στο Τ⁺ που αποτελούνται από ίσο αριθμό από 0 και 1.

Άσκηση 3.2.1: (Α) Διατυπώστε κανόνες για μια ΓΧΣ που παράγει όλες τις συμβολοσειρές από το αλφάβητο Τ={α, β} της μορφής αⁿβⁿ, όπου n 1, και μόνο αυτές. (Β) Πώς πρέπει να τροποποιηθούν οι κανόνες ώστε να περιλάβουν και την περίπτωση n = 0;

Σημείωση: από εδώ και στο εξής, σε παρόμοιες ασκήσεις, το «και μόνο αυτές» θα το παραλείπουμε ως εννοούμενο.

Άσκηση 3.2.2: Διατυπώστε κανόνες για μια ΓΧΣ που παράγει όλες τις συμβολοσειρές από το αλφάβητο Τ={α, β} της μορφής αⁿβⁿ⁺¹, όπου n 1.

Άσκηση 3.2.3: Διατυπώστε κανόνες για μια ΓΧΣ που παράγει όλες τις συμβολοσειρές από το αλφάβητο Τ={α, β} της μορφής αⁿβ^m, όπου n > m, και n, m 1

Άσκηση 3.2.4: Διατυπώστε κανόνες για μια ΓΧΣ που παράγει όλες τις συμβολοσειρές από το αλφάβητο Τ={α, β} οι οποίες είναι παλίνδρομα. (Θυμίζουμε οτι η κενή συμβολοσειρά είναι κι αυτή παλίνδρομο.)

Άσκηση 3.2.5: Έχοντας λύσει την προηγούμενη άσκηση (3.2.4), διατυπώστε κανόνες για μια ΓΧΣ που παράγει όλες τις συμβολοσειρές από το αλφάβητο Τ={α, β} οι οποίες έχουν άρτιο μήκος (μπορεί και 0), και αν χωριστούν στη μέση τότε τα α και β στα δύο μισά αποτελούν “αντικατοπτρισμό” το ένα του άλλου (όπως π.χ. στα ααβ·αββ, αβαββββα·βααααβαβ, κλπ, όπου με · σημειώσαμε το μέσον, χωρίς αυτό το σύμβολο να ανήκει στη συμβολοσειρά).

3.3 Παραγωγικά δέντρα

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

1. Έκφραση → Όρος + Όρος | Όρος – Όρος | Όρος

2. Όρος → Παράγοντας * Παράγοντας | Παράγοντας / Παράγοντας | Παράγοντας

3. Παράγοντας → ( Έκφραση ) | Έκφραση

4. Έκφραση → Μεταβλητή | ΦυσικόςΑριθμός

5. Μεταβλητή → x | y | z

6. ΦυσικόςΑριθμός → Ψηφίο_0 | Ψηφίο19 Ψηφία

7. Ψηφία → Ψηφίο_0 Ψηφία | Ψηφίο19 Ψηφία | Ψηφίο_0 | Ψηφίο19

8. Ψηφίο19 → 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

9. Ψηφίο_0 → 0

Οπως είδαμε, η συμβολοσειρά 0 * x + (2 / 0) παράγεται από τη γραμματική αυτή, δηλαδή:

Έκφραση 0 * x + (2 / 0)

Αυτή όμως η παράσταση της παραγωγής δεν μας δίνει την πλήρη πληροφορία του πώς παρήχθη τελικά η συμβολοσειρά, δηλαδή μέσω ποιων βημάτων (αντικαταστάσεων μεταβλητών μέσω κανόνων). Θα μπορούσαμε να γράψουμε:

Έκφραση Όρος Παράγοντας * Παράγοντας ... 0 * x + (2 / 0)

με μια μακριά αλυσίδα παραγωγών. Ένας όμως πιο παραστατικός τρόπος της πλήρους παραγωγής δίνεται μέσω του ακόλουθου δέντρου:

Εικ. 3.3.1: Παραγωγικό δέντρο για την έκφραση 0 * x + (2 / 0)

Το δεντρο αυτό λέγεται παραγωγικό δέντρο (αγγλ.: parse tree, ή derivation tree). Πιο συγκεκριμένα:

Ορισμός: Έστω G = (V, T, P, S) μια ΓΧΣ Ένα δέντρο ονομάζεται παραγωγικό δέντρο για τη G αν:

1. Σε κάθε κορυφή αντιστοιχεί μια ετικέτα, δηλαδή ένα σύμβολο από το V T { ε }.

2. Η ετικέτα της ρίζας είναι το S.

3. Αν μια κορυφή είναι εσωτερική (όχι φύλλο του δέντρου) και έχει ετικέτα το Α, τότε πρέπει Α V.

4. Αν η κορυφή n έχει ετικέτα Α, και είναι γονέας των τέκνων n₁, n₂, ... n_k, με αυτή τη διάταξη από αριστερά προς τα δεξιά, με ετικέτες Χ₁, Χ₂, ... Χ_k αντίστοιχα, τότε το Α → Χ₁Χ₂...Χ_k πρέπει να είναι ένας κανόνας του P.

5. Αν η κορυφή n έχει ετικέτα ε, τότε το n πρέπει να είναι φύλλο και μοναδικό τέκνο του γονέα-του.

Άσκηση 3.3.2: Κατασκευάστε το παραγωγικό δέντρο για την παραγωγή της συμβολοσειράς 0011 μέσω της γραμματικής που διατυπώσατε στη λύση της άσκησης 3.2.1.

Ορισμός: Ένα υποδέντρο (αγγλ.: subtree) ενός παραγωγικού δέντρου είναι μία κορυφή του παραγωγικού δέντρου μαζί με όλους τους απογόνους-της, δηλαδή όλες τις κορυφές (είτε εσωτερικές είτε φύλλα) για τις οποίες υπάρχουν διαδρομές προς αυτές από την κορυφή. Αν η ετικέτα της ρίζας του υποδέντρου είναι το Α, τότε στο υποδέντρο αυτό αναφερόμαστε ως Α-δέντρο.

Συνεπώς, “S-δέντρο” είναι ένας εναλλακτικός τρόπος να αναφερθούμε στο συνολικό παραγωγικό δέντρο.

Ορισμός: Έστω ένα υποδέντρο μιας ΓΧΣ. Το προϊόν (αγγλ.: yield) του υποδέντρου είναι η συμβολοσειρά που προκύπτει αν επισκεφθούμε τις κορυφές του υποδέντρου αναδρομικά και με κατά βάθος προτεραιότητα (αγγλ.: depth-first), από αριστερά προς τα δεξιά, και παραθέσουμε τα τερματικά σύμβολα που συναντάμε κατά την επίσκεψη αυτή.

Παράδειγμα: η συμβολοσειρά 0 * x + (2 / 0) είναι το προϊόν του παραγωγικού δέντρου του αρχικού παραδείγματος αυτής της υποενότητας.

Ισχύει επίσης το εξής:

Θεώρημα 3.3.1: Έστω G = (V, T, P, S) μια ΓΧΣ. Τότε S α αν και μόνο αν υπάρχει παραγωγικό υποδέντρο στην G με προϊόν το α.

Η απόδειξη του παραπάνω θεωρήματος είναι εκτός του εύρους του παρόντος μαθήματος.

Ορισμός: Αν σε καθε βήμα της παραγωγής ενός προϊόντος επιλέγεται προς αντικατάσταση μέσω ενός κανόνα-της η πιο αριστερά ευρισκόμενη μεταβλητή, τότε η παραγωγή αυτή λέγεται αριστερή παραγωγή. Αντίστοιχα, αν επιλέγεται πάντα η πιο δεξιά ευρισκόμενη μεταβλητή, τότε η παραγωγή λέγεται δεξιά παραγωγή.

Παράδειγμα: Έστω η ΓΧΣ. G = (V, T, P, S) με V = {S, A, B}, T = {α, β}, και P το εξής:

• S → αΑ | αΒ

• Α → α | ΑΒ

• Β → β | αβ

Τότε η συμβολοσειρά ααβ έχει την εξής αριστερή παραγωγή:

S αΑ αΑΒ ααΒ ααβ

Έχει όμως και την ακόλουθη δεξιά παραγωγή:

S αΑ αΑΒ αΑβ ααβ

Όπως βλέπουμε, στο τρίτο βήμα παραγωγής, από τη συμβολοσειρά αΑΒ επιλέγεται προς αντικατάσταση το Α όταν έχουμε αριστερή παραγωγή, ενώ το Β όταν έχουμε δεξιά παραγωγή.

Στο παραπάνω παράδειγμα συμβαίνει και κάτι άλλο: η συμβολοσειρά ααβ έχει δύο διαφορετικές παραγωγές (και αντίστοιχα παραγωγικά δέντρα):

1. S αΑ αΑΒ ααΒ ααβ

2. S αΒ ααβ

Ορισμός: Μια ΓΧΣ G της οποίας κάποιο προϊόν έχει δύο διαφορετικά παραγωγικά δέντρα ονομάζεται διφορούμενη (ή ασαφής, ή αμφίσημη· αγγλ.: ambiguous).

Παράδειγμα: Η ΓΧΣ του προηγούμενου παραδείγματος είναι προφανώς διφορούμενη, αφού η συμβολοσειρά ααβ, όπως είδαμε, έχει δύο διαφορετικά παραγωγικά δέντρα.

Ορισμός: Μια γλώσσα χωρίς συμφραζόμενα της οποίας κάθε ΓΧΣ είναι διφορούμενη, ονομάζεται εγγενώς διφορούμενη γλώσσα.

Παράδειγμα: Μπορεί να αποδειχθεί (αν και η απόδειξη είναι αρκετά περίπλοκη) οτι η γλώσσα:

L = { αⁿβⁿγ^mδ^m | n 1, m 1 } { αⁿβ^mγ^mδⁿ | n 1, m 1 }

είναι εγγενώς διφορούμενη.

Η έννοια της εγγενώς διφορούμενης γλώσσας είναι πολύ σημαντική στις γλώσσες προγραμματισμού, όπου, για λόγους αποδοτικότητας (ταχύτητας) των μεταγλωττιστών, αποφεύγουμε μια γλώσσα προγραμματισμού να είναι εγγενώς διφορούμενη. Πρακτικά όλες οι γνωστές γλώσσες προγραμματισμού είναι μη διφορούμενες.

3.4 Απλοποιήσεις σε ΓΧΣ

Οι κανόνες των ΓΧΣ είναι δυνατό να απλοποιηθούν σημαντικά μέσω διάφορων αυτοματοποιημένων μεθόδων (αλγορίθμων). Μια γραμματική μπορεί να περιλαμβάνει άχρηστα σύμβολα, κενούς κανόνες, και/ή μοναδιαίους κανόνες. Ας δούμε, μία-μία, αυτές τις περιπτώσεις.

3.4.1 Άχρηστα σύμβολα

Ορισμός: Έστω G = (V, T, P, S) μια ΓΧΣ. Ένα σύμβολο Χ V T ονομάζεται χρήσιμο αν υπάρχει παραγωγή της μορφής S aXb w, όπου a, b (V T)^* και w T^*. Αλλιώς το Χ ονομάζεται άχρηστο.

Σύμφωνα με τον παραπάνω ορισμό, για να είναι το Χ χρήσιμο, πρέπει να συμβαίνουν δύο πράγματα: πρώτο, πρέπει το Χ να μπορεί να παραγάγει κάποια συμβολοσειρά αποτελούμενη από τερματικά σύμβολα (X w)· και δεύτερο, το Χ πρέπει να εμφανίζεται σε μια συμβολοσειρά που παράγεται από το S (S aXb). Ας δούμε έναν αλγόριθμο μέσω του οποίου βρίσκουμε όλα τα Χ τέτοια ώστε X w για κάποιο w T^*.

έστω σύνολο ΠαλαιόV ←

έστω σύνολο ΝέοV ← { Α | Α → w για κάποιο w T^* }

όσο ΠαλαιόV ΝέοV επανάλαβε:

ΠαλαιόV ← ΝέοV

ΝέοV ← ΠαλαιόV { Α | Α → a για κάποιο a (Τ ΠαλαιόV)^* }

Το νέο σύνολο μεταβλητών είναι το ΝέοV.

Ας κάνουμε μια εφαρμογή του παραπάνω αλγορίθμου. Έστω η ΓΧΣ G = (V, T, P, S) με το εξής σύνολο κανόνων Ρ:

• S → Αα | ΑΒ

• Α → αC | β

• Β → ΒΑ

• C → Αα

Ξεκινάμε τον αλγόριθμο με τα σύνολα ΠαλαιόV ίσο με , και ΝέοV = { Α }, λόγω του κανόνα Α → β, εφόσον β T.

Μπαίνοντας στην ανακύκλωση του αλγορίθμου (εφόσον ΠαλαιόV ΝέοV), θέτουμε ΠαλαιόV ← { Α }, και στο αμέσως επόμενο βήμα, ΝέοV ← { Α } { C }, εφόσον υπάρχει ο κανόνας C → Αα, και Αα (Τ { Α })^*. Άρα τώρα ΝέοV είναι το { Α, C }.

Συνεχίζουμε στην ανακύκλωση γιατί ΠαλαιόV ΝέοV. Θέτουμε ΠαλαιόV ← { Α, C }. Τώρα όμως δεν μπορούμε να βρούμε άλλον κανόνα ώστε να επεκτείνουμε το ΝέοV. Έτσι ΠαλαιόV = ΝέοV, οπότε βγαίνουμε από την ανακύκλωση, και το νέο σύνολο μεταβλητών είναι το { Α, C }. Επομένως απαλλαχθήκαμε από τη μεταβλητή Β.

Με ένα δεύτερο, πολύ απλό αλγόριθμο, δοσμένης μιας ΓΧΣ G = (V, T, P, S), μπορούμε να βρούμε μια ισοδύναμη ΓΧΣ G΄ = (V΄, T΄, P΄, S) τέτοια ώστε για κάθε Χ (V΄ T΄) να υπάρχουν a και b (V΄ T΄)^* για τα οποία να ισχύει S aΧb. Οπότε θα ικανοποιηθεί και η δεύτερη συνθήκη περί χρήσιμων συμβόλων. Ο αλγόριθμος αυτός είναι ο εξής:

έστω σύνολα V΄ ← { S } και Τ΄ ←

για κάθε Α V΄ που δεν έχει εξεταστεί ακόμη, και με κανόνα Α → w επανάλαβε:

βάλε όλες τις μεταβλητές του w στο V΄

βάλε όλα τα τερματικά του w στο Τ΄

Το Ρ΄ είναι το σύνολο των κανόνων του Ρ που περιέχουν μόνο σύμβολα από το V΄ T΄.

Ας παρατηρήσουμε οτι οι παραπάνω δύο αλγόριθμοι πρέπει να εφαρμοστούν με τη σειρά που αναφέρθηκαν (βλ. άσκηση 3.4.2).

Με εφαρμογή τόσο του 1ου όσο και του 2ου αλγορίθμου, το σύμβολο Β κρίνεται άχρηστο, και ο κανόνας Β → ΒΑ δεν περιλαμβάνεται στην τελική γραμματική.

Άσκηση 3.4.1: Έστω η γραμματική με κανόνες:

• S → ΑΒ | α

• Α → α

Εφαρμόστε τους δύο παραπάνω αλγορίθμους για να την απαλλάξετε από άχρηστα σύμβολα και κανόνες.

Άσκηση 3.4.2: Τί θα συμβεί στην προηγούμενη άσκηση αν εφαρμόσουμε πρώτα το 2ο αλγόριθμο, και μετά τον 1ο;

3.4.2 Κενοί κανόνες

Αν η L(G) μιας ΓΧΣ G περιλαμβάνει την κενή συμβολοσειρά ε, ασφαλώς δεν μπορούμε να απαλείψουμε όλους τους κανόνες της μορφής Α → ε. Αν όμως το ε δεν περιλαμβάνεται στην L(G), τότε μπορούμε να απαλείψουμε κάθε τέτοιον κενό κανόνα.

Ορισμός: Έστω G = (V, T, P, S) μια ΓΧΣ. Μια μεταβλητή Α V ονομάζεται μηδενίσιμη αν Α ε.

Προκειμένου να απαλείψουμε τους κανόνες της μορφής Α → ε κάνουμε το εξής:

Κάθε κανόνα της μορφής Β → Χ₁Χ₂ ... Χ_n τον αντικαθιστούμε με όλους τους κανόνες που προκύπτουν διαγράφοντας κάθε δυνατό υποσύνολο από εκείνα τα Χ_i που είναι μηδενίσιμα.

Δεν περιλαμβάνουμε όμως τον κανόνα Β → ε ακόμα και αν όλα τα Χ_i είναι μηδενίσιμα.

Φυσικά, ο παραπάνω αλγόριθμος μπορεί να αυξήσει κατά εκθετικό τρόπο το πλήθος των κανόνων στη νέα γραμματική.

3.4.3 Μοναδιαίοι κανόνες

Είναι επίσης δυνατό να απαλείψουμε κάθε μοναδιαίο κανόνα της μορφής Α → Β, όπου Α, Β V.

Έστω G = (V, T, P, S) μια ΓΧΣ όπου η L(G) δεν περιλαμβάνει το ε. Μπορούμε ήδη να υποθέσουμε οτι η G δεν έχει κενούς κανόνες. Κατασκευάζουμε ένα νέο σύνολο κανόνων Ρ΄ από το Ρ ως εξής:

Πρώτα περιλαμβάνουμε όλους τους μη-μοναδιαίους κανόνες του Ρ στο Ρ΄.

Κατόπιν, ας υποθέσουμε οτι Α Β, για Α, Β V. Προσθέτουμε στο Ρ΄ όλους τους κανόνες της μορφής Α → w, όπου το Β → w είναι ένας μη-μοναδιαίος κανόνας του Ρ.

3.5 Κανονική μορφή του Τσόμσκι

Θεώρημα 3.5.1: Κάθε L(G) χωρίς το ε, μιας ΓΧΣ G μπορεί να παραχθεί από μια γραμματική G΄ της οποίας όλοι οι κανόνες είναι της μορφής Α → ΒC, ή Α → α, όπου τα Α, Β, και C είναι μεταβλητές, και το α τερματικό σύμβολο.

Οι γραμματικές του θεωρήματος 3.5.1 λέμε οτι είναι στην κανονική μορφή του Τσόμσκι.

Δεν θα αποδείξουμε το θεώρημα, θα δώσουμε όμως τον ακόλουθο αλγόριθμο που μετατρέπει μια ΓΧΣ σε κανονική μορφή του Τσόμσκι.

Πρώτα, βάσει των αλγορίθμων που έχουν δοθεί μέχρι στιγμής, βρίσκουμε μια ισοδύναμη γραμματική που δεν έχει κενούς κανόνες, ούτε μοναδιαίους κανόνες.

Συνεπώς αν ένας κανόνας έχει ένα μόνο σύμβολο στα δεξιά, αυτό το σύμβολο πρέπει να είναι τερματικό, άρα ο κανόνας αυτός είναι ήδη στην επιθυμητή μορφή.

Θεωρούμε τώρα κανόνες της μορφής Α → Χ₁Χ₂ ... Χ_n όπου n 2. Αν το Χ_i είναι το τερματικό α, εισάγουμε μια νέα μεταβλητή Β_α και τον κανόνα Β_α → α, που είναι σε επιθυμητή μορφή, και αντικαθιστούμε το Χ_i με το Β_α. Επομένως τώρα όλοι οι κανόνες είναι της μορφής είτε Α → α, είτε Α → Β₁Β₂ ... Β_n όπου n 2. Αν n = 2, τότε ο κανόνας είναι της επιθυμητής μορφής. Αν n 3, τότε δημιουργούμε νέες μεταβλητές C₁, C₂, ..., C_n–2 και αντικαθιστούμε τον κανόνα Α → Β₁Β₂ ... Β_n με το σύνολο των κανόνων:

• Α → Β₁C₁

• C₁ → Β₂C₂

• ...

• C_n–3 → Β_n–2C_n–2

• C_n–2 → Β_n–1Β_n

Το οποίο είναι σύνολο κανόνων της επιθυμητής μορφής, δηλαδή της κανονικής μορφής του Τσόμσκι.

4. Αυτόματα Στοίβας

4.1 Εισαγωγικές έννοιες και ορισμοί

Στην ενότητα 2 γνωρίσαμε τα πεπερασμένα αυτόματα και τις κανονικές εκφράσεις, και είδαμε οτι πρόκειται για μηχανισμούς που αναγνωρίζουν ένα αρκετά περιορισμένο σύνολο γλωσσών. Στην ενότητα 3 επεκτείναμε αυτό το σύνολο γλωσσών μέσω της γραμματικής χωρίς συμφραζόμενα (ΓΧΣ). Στην παρούσα ενότητα θα γνωρίσουμε έναν άλλο μηχανισμό, ένα είδος αυτομάτου, το οποίο θα έχει τις ίδιες ικανότητες με τις ΓΧΣ, θα αναγνωρίζει δηλαδή το ίδιο σύνολο γλωσσών: τις γλώσσες χωρίς συμφραζόμενα.

Ο μηχανισμός αυτός λέγεται αυτόματο στοίβας, και μοιάζει πολύ με ένα πεπερασμένο αυτόματο, συγκεκριμένα με ένα ΜΠΑ, καθώς είναι κι αυτό μη-αιτιοκρατικό, με τη διαφορά οτι περιλαμβάνει έναν επιπλέον μηχανισμό που λέγεται στοίβα. Η στοίβα είναι μια περιοχή μνήμης όπου γράφονται σε μια σειρά σύμβολα από ένα αλφάβητο, εν γένει διαφορετικό από το αλφάβητο της εισόδου του αυτομάτου. Ο τρόπος που η στοίβα ενημερώνεται με σύμβολα είναι ο εξής: σύμβολα μπορούν να εισαχθούν μόνο από το ένα άκρο της στοίβας, το οποίο θα ονομάσουμε “κορυφή”· αλλά επίσης μπορούν να διαγραφούν μόνο από την κορυφή. Έτσι, όταν ένα σύμβολο εισάγεται στη στοίβα από την κορυφή-της, είναι και το σύμβολο που έχει προτεραιότητα να εξεταστεί ή και να διαγραφεί από τη στοίβα, κάνοντας μικρότερη την προτεραιότητα όλων των άλλων συμβόλων. Η στοίβα μοιάζει με μια πραγματική στοίβα από άδεια πιάτα, από την οποία παίρνουμε πάντα το κορυφαίο πιάτο όταν χρειαζόμαστε ένα, και στην οποία βάζουμε πάντα τα νέα άδεια πιάτα από την κορυφή. Αν η στοίβα αδειάσει εντελώς, λέμε οτι αποκαλύφθηκε ο “πυθμένας” της στοίβας (ο οποίος δεν είναι σύμβολο, είναι απλώς η άδεια στοίβα). Την κενή στοίβα ια τη συμβολίζουμε με το ε.

Παράδειγμα:

Εικ. 4.1.1: Σχηματική παράσταση στοίβας

Στο διάγραμμα 4.4.1, στην κορυφή της στοίβας βρίσκεται το σύμβολο υ, ενώ τα σύμβολα ω, ψ, χ, και φ, εισήχθησαν νωρίτερα στη στοίβα, με αυτή τη σειρά (δηλ. πρώτο το ω, μετά το ψ, κλπ). Αν το υ, που είναι στην κορυφή, διαβαστεί και αφαιρεθεί από τη στοίβα, το επόμενο σύμβολο που θα μπορεί να διαβαστεί (και ίσως να αφαιρεθεί) θα είναι το φ, κ.ο.κ. Αν προστεθεί ένα νέο σύμβολο, π.χ. το τ, αυτό θα τοποθετηθεί στην κορυφή της στοίβας, που έτσι θα μεγαλώσει κατά 1 σε μήκος. Αν ποτέ αφαιρεθεί και το ω, τότε θα αποκαλυφθεί ο πυθμένας και η στοίβα θα γίνει κενή.

Σηνειώνουμε οτι η στοίβα είναι απλώς ένας επιπλέον μηχανισμός του αυτομάτου στοίβας, που κατά τα άλλα διαθέτει και την ταινία των συμβόλων εισόδου που διαθέτει και ένα ΜΠΑ. Ας κάνουμε τώρα όλα αυτά συγκεκριμένα.

Ορισμός: Ένα αυτόματο στοίβας (ΑΣ· αγγλ.: pushdown automaton) είναι μια επτάδα (Q, Σ, Γ, δ, q₀, Ζ₀, F), όπου:

1. Το Q είναι ένα πεπερασμένο σύνολο καταστάσεων, όπως και στα ΠΑ.

2. Το Σ είναι ένα σύνολο συμβόλων, το αλφάβητο εισόδου, όπως και στα ΠΑ.

3. Το Γ είναι ένα σύνολο συμβόλων, το αλφάβητο στοίβας, όχι κατ’ ανάγκη διαφορετικό από το Σ.

4. Το δ είναι μια απεικόνιση από το Q X (Σ {ε}) X Γ σε πεπερασμένα υποσύνολα του Q X Γ^*.

5. Το q₀ Q είναι η αρχική κατάσταση, όπως και στα ΠΑ.

6. Το Ζ₀ Γ είναι ένα συγκεκριμένο σύμβολο που ονομάζεται αρχικό σύμβολο στοίβας.

7. Τέλος, το F Q είναι το σύνολο των τελικών καταστάσεων, όπως και στα ΠΑ.

Θα χρησιμοποιούμε σύμβολα από την αρχή του αλφαβήτου (α, β, γ, ...) για το αλφάβητο εισόδου, και σύμβολα από το τέλος του αλφαβήτου (..., χ, ψ, ω) για το αλφάβητο στοίβας. Κατά τα άλλα, οι συμβάσεις-μας περί συμβόλων παραμένουν όπως πριν.

Αναφορικά με την απεικόνιση δ, έχουμε να πούμε τα εξής. Η γραφή:

δ (q, α, χ) = {(q₁, χ₁), (q₂, χ₂), ..., (q_n, χ_n)}

όπου q, q_i Q, 1 i n, α Σ, χ Γ, και χ_i Γ^*, 1 i n, σημαίνει οτι το ΑΣ, ευρισκόμενο σε κατάσταση q, με α ως σύμβολο εισόδου, και χ ως σύμβολο κορυφής της στοίβας, μπορεί να μεταφερθεί σε οποιαδήποτε κατάσταση από τις q_i, αντικαθιστώντας το χ στη στοίβα με το αντίστοιχο χ_i. Πρόκειται δηλαδή για ένα μη-αιτιοκρατικό αυτόματο. Επίσης, η γραφή:

δ (q, ε, χ) = {(q₁, χ₁), (q₂, χ₂), ..., (q_n, χ_n)}

σημαίνει οτι το ΑΣ, ευρισκόμενο σε κατάσταση q, ανεξάρτητα από το σύμβολο εισόδου, και με το χ ως σύμβολο κορυφής της στοίβας, πράττει όπως ανωτέρω. Στην περίπτωση αυτή, η νοητή “κεφαλή” που διαβάζει την είσοδο δεν προχωράει για να διαβάσει το επόμενο σύμβολο εισόδου, αλλά παραμένει ακίνητη.

Υπάρχουν, επομένως, τα παραπάνω δύο είδη “κινήσεων” που μπορεί να κάνει ένα ΑΣ: το ένα είδος κίνησης παίρνει υπόψη τα περιεχόμενα της εισόδου, και το άλλο τα αγνοεί.

4.2 Αποδοχή γλώσσας: πότε τα ΑΣ κάνουν αποδοχή της εισόδου

Κάτι που λείπει από τον παραπάνω ορισμό είναι το πότε το ΑΣ σταματάει και αποδέχεται την είσοδο που του δόθηκε. Υπάρχουν δύο τρόποι για να σταματήσει ένα ΑΣ, που τελικά αποδεικνύεται οτι είναι ισοδύναμοι μεταξύ-τους:

1. Όπως και στα ΠΑ, δηλαδή με την άφιξη σε τελική κατάσταση q F. Το ΑΣ αποδέχεται τη συμβολοσειρά που το οδήγησε στην q.

2. Μέσω αδειάσματος της στοίβας. Όταν δηλαδή η στοίβα αδειάσει, το ΑΣ αποδέχεται τη συμβολοσειρά που το οδήγησε σε άδειασμα της στοίβας.

Αν Μ είναι το ΑΣ, τη γλώσσα της περίπτωσης 1 θα τη συμβολίζουμε με το L(Μ), ενώ τη γλώσσα της περίπτωσης 2 με το Ν(Μ).

Θεώρημα 4.2.1: Αν η γλώσσα L είναι L(M₁) για κάποιο ΑΣ M₁, τότε η L είναι Ν(M₂) για κάποιο ΑΣ M₂.

Θεώρημα 4.2.2: Αν η γλώσσα L είναι Ν(M₂) για κάποιο ΑΣ M₂, τότε η L είναι L(M₁) για κάποιο ΑΣ M₁.

Με άλλα λόγια, όπως ειπώθηκε στην εισαγωγική υποενότητα, ο τερματισμός με άφιξη σε τελική κατάσταση είναι ισοδύναμος με τον τερματισμό λόγω αδειάσματος της στοίβας. Οι αποδείξεις των δύο θεωρημάτων είναι απλές εννοιολογικά αλλά περίπλοκες στις λεπτομέρειές τους, και ο αναγνώστης μπορεί να τις βρει στο [1]· ας δει επίσης την άσκηση 4.2.1, παρακάτω.

Παράδειγμα ενός ΑΣ που τερματίζει μέσω αδειάσματος της στοίβας:

Εικ. 4.2.1: Αυτόματο Στοίβας για παλίνδρομα

Το ΑΣ της Εικ. 4.2.1 αποδέχεται τη γλώσσα: { ww^R | w (0 + 1)^*}, δηλαδή τη γλώσσα των παλινδρόμων. Έχουμε: Q = {q₁, q₂}, Σ = {0, 1}, ενώ ως αλφάβητο στοίβας Γ χρησιμοποιούνται τρία σύμβολα με χρώμα: {●, ●, ●} (κόκκινο, πράσινο, μπλε). Αρχική κατάσταση είναι η q₁, αρχικό σύμβολο στη στοίβα είναι το Ζ₀ = ●, ενώ το σύνολο των τελικών καταστάσεων F είναι το (το αυτόματο τερματίζει λόγω κενής στοίβας).

Στην Εικ. 4.2.1, πάνω σε κάθε μεγάλο τόξο που αντιστοιχεί σε μια μετάβαση της δ, εμφανίζεται η περιγραφή της μετάβασης με ένα βέλος (→), αριστερά του οποίου είναι η συνθήκη της μετάβασης (το πότε γίνεται), όπως π.χ. έτσι: 0, ●→ όπου 0 είναι το σύμβολο εισόδου, ενώ το ● είναι το σύμβολο της στοίβας. Η συγκεκριμένη συνθήκη λοιπόν λέει: «Με 0 ως σύμβολο εισόδου, και ● ως σύμβολο στοίβας,...» Δεξιά του βέλους φαίνεται το τί συμβαίνει στη στοίβα. Η εισαγωγή συμβόλου στη στοίβα δείχνεται σχηματικά όποτε έχουμε δύο από τις χρωματιστές κουκκίδες–σύμβολα του Γ, τη μία πάνω στην άλλη, με την κάτω κουκκίδα να είναι αυτή που υπήρχε στην κορυφή της στοίβας, και την άνω κουκκίδα να είναι αυτή που εισάγεται και γίνεται η νέα κορυφή. Εξαγωγή από τη στοίβα έχουμε όποτε εμφανίζεται το ε δεξιά από το βέλος, δηλαδή έτσι: → ε.

Παρατηρούμε οτι το ΑΣ αυτό είναι μη-αιτιοκρατικό γιατί σε δύο περιπτώσεις από την κατάσταση q₁ έχουμε δύο επιτρεπτές μεταβάσεις: τη μία με συνθήκη 0, ●, και την άλλη με συνθήκη 1, ●. Π.χ. στη συνθήκη 0, ● έχουμε τη μετάβαση στην q₂ κάνοντας εξαγωγή συμβόλου από τη στοίβα (→ ε), αλλά και τη μετάβαση πίσω στην q₁, εισάγοντας ένα επιπλέον ● στη στοίβα.

Η “λογική” του ΑΣ αυτού είναι, αφού ξεκινήσει τη στοίβα με ●, όποτε συναντά το 0 στην είσοδο να εισάγει στη στοίβα το ●· και όποτε συναντά το 1 στην είσοδο να εισάγει στη στοίβα το ●. Ταυτόχρονα όμως, “μαντεύει” ανά πάσα στιγμή (εδώ έγκειται η μη-αιτιοκρατικότητά του) οτι μπορεί να φτάσαμε στο μέσον του παλιδρόμου, οπότε μεταβαίνει στην q₂ και αρχίζει να κάνει εξαγωγές από τη στοίβα, με το χρώμα να αναμένεται να αντιστοιχεί με το σύμβολο εισόδου: ● για 0, και ● για 1. Αν κάποια αντιστοιχία αποτύχει, το αυτόματο σταματά γιατί δεν έχει κατάλληλη μετάβαση, επομένως απορρίπτει την είσοδο («δεν είναι παλίνδρομο»). Αν όλες οι αντιστοιχίες πετύχουν και βρεθεί το ● (στον πυθμένα της στοίβας), εξάγεται και το ● και η στοίβα μένει κενή, οπότε η είσοδος γίνεται αποδεκτή («είναι παλίνδρομο»).

Άσκηση 4.2.1: Έχοντας το παραπάνω παράδειγμα κατά νου, σκεφτείτε πώς θα πρέπει να λειτουργούν οι αποδείξεις των θεωρημάτων 4.2.1 και 4.2.2.

4.3 Ισοδυναμία ΑΣ με ΓΧΣ

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

Θεώρημα 4.3.1: Αν η L είναι μια γλώσσα χωρίς συμφραζόμενα, τότε υπάρχει ένα ΑΣ Μ τέτοιο ώστε L = N(M).

Θεώρημα 4.3.2: Αν η γλώσσα L είναι Ν(Μ) για κάποιο ΑΣ Μ, τότε η L είναι γλώσσα χωρίς συμφραζόμενα.

Επειδή οι αποδείξεις των θεωρημάτων αυτών γίνονται πιο εύκολα όταν θεωρούμε ΑΣ με τερματισμό λόγω αδειάσματος στοίβας, αυτός είναι και ο λόγος που έχουμε ορίσει τον τερματισμό αυτόν· αλλιώς θα αρκούσε να μιλάμε για τερματισμό λόγω άφιξης σε τελική κατάσταση.

4.4 Αιτιοκρατικά ΑΣ

Η όλη παρουσίαση των ΑΣ μέχρι τώρα περιλαμβάνει μόνο μη-αιτιοκρατικές μηχανές, που αποδεικνύονται ισοδύναμες με τις ΓΧΣ.

Άσκηση 4.4.1: Τροποποιήστε τον ορισμό των ΑΣ ώστε να ορίζει μόνο αιτιοκρατικά ΑΣ.

Τί συμβαίνει όμως αν περιορίσουμε τα ΑΣ ώστε να συμπεριφέρονται αιτιοκρατικά; Έχουμε μήπως τότε την ίδια κατάσταση με τα πεπερασμένα αυτόματα, όπου στην ενότητα 2 αποδείξαμε οτι αιτιοκρατικά (ΑΠΑ) και μη-αιτιοκρατικά (ΜΠΑ) αυτόματα είναι ισοδύναμα;

Η απάντηση είναι οτι όχι, στα ΑΣ αυτό δεν συμβαίνει. Τα αιτιοκρατικά ΑΣ αποδεικνύεται οτι είναι ασθενέστερα από τα μη-αιτιοκρατικά ΑΣ, με την έννοια οτι υπάρχουν γλώσσες χωρίς συμφραζόμενα που αναγνωρίζονται από μη-αιτιοκρατικά ΑΣ, και για τις οποίες δεν υπάρχει αιτιοκρατικό ΑΣ που να τις αναγνωρίζει. Παράδειγμα μιας τέτοιας γλώσσας είναι η γλώσσα των παλινδρόμων: { ww^R | w (0 + 1)^*}.

Άσκηση 4.4.2: Τροποποιήστε το παράδειγμα της υποενότητας 4.2 ώστε να ορίσετε ένα αιτιοκρατικό ΑΣ που να αποδέχεται τη γλώσσα { w2w^R | w (0 + 1)^*}, με Σ = {0, 1, 2}.