Αυτόματα στοίβας (Pushdown Automata ή PDA)
Τα αυτόματα στοίβας (ΑΣ) είναι μηχανές οι οποίες παράγουν γλώσσες χωρίς συμφραζόμενα (type 2).
Η διαφορά του με τα πεπερασμένα αυτόματα (για κανονικές γραμματικές, type 3) που είδαμε μέχρι τώρα βρίσκεται στο ότι τα PDA έχουν περισσότερη μνήμη σε μορφή στοίβας (stack).
Η στοίβα έχει απεριόριστη μνήμη και οι δύο βασικές εντολές είναι push και pop.
Ένα PDA μπορεί να κάνει δεκτή ή μη αποδεκτή μια συμβολοσειρά όπως και τα περερασμένα αυτόματα.
Με τα αυτόματα στοίβας μπορούμε να παράξουμε γλώσσες της μορφής: R = anbn.
Οι γλώσσες που παράγονται από τα ΑΣ είναι ένα υπερσύνολο των γλωσσών που παράγονται από τα ντετερμινιστικά πεπερασμένα αυτόματα που είδαμε στα προηγούμενα κεφάλαια.
Τυπικός ορισμός
Ένα αυτόματο στοίβας ορίζεται ως μία πλειάδα επτά (7) στοιχείων: P = (K, Σ, s, F, δ, Γ, z0) όπου:
- K (ή Q) είναι ένα πεπερασμένο σύνολο καταστάσεων
- Σ είναι ένα αλφάβητο (πεπερασμένο σύνολο συμβόλων)
- s ή (q0) ∈ K είναι η αρχική κατάσταση
- F ⊆ K είναι το σύνολο των τελικών καταστάσεων και
- δ είναι μία σχέση μετάβασης
- Γ είναι ένα αλφάβητο στοίβας (πεπερασμένο σύνολο συμβόλων)
- z0 είναι το αρχικό σύμβολο της στοίβας
Η σχέση μετάβασης έχει την εξής μορφή: δ(q, a, X)
όπου:
q
μια κατάσταση από το σύνολο Κ (ή Q)a
σύμβολο από το αλφάβητο Σ ή a = εX
σύμβολο στην κορυφή της στοίβας από το σύνολο Γ
Για κάθε σετ ορισμάτων στην δ
έχουμε ως αποτέλεσμα (output) ένα ζεύγος της μορφής: (p, γ)
όπου:
p
μια νέα κατάστασηγ
συμβολοσειρά από το Γ που αντικαθιστά το X στην κορυφή της στοίβας.
Διακρίνουμε τις παρακάτω περιπτώσεις σχετικά με την τιμή του γ
.
γ = ε
Έχουμε pop στην στοίβαγ = X
Δεν έχουμε αλλαγή στην στοίβαγ = YZ
Αντικατάσταση του X με το Z και push το Y ή pop το X και push το Z και μετά το Y
Σχηματική αναπαράσταση
Για κάθε μετάβαση πρέπει να δείχνουμε και τις αλλαγές στην στοίβα εκτός από την μετάβαση σε κατάσταση όπως κάναμε στα πεπερασμένα αυτόματα.
Η έκφραση b→c
δείχνει ότι το b πρέπει να γίνει pop και το c να γίνει push.
Αν b = ε
δεν έχουμε pop όπως επίσης αν c = ε
δεν έχουμε push.
Μπορεί επίσης να ισχύει a = ε
αφού το αυτόματο στοίβας δεν είναι ντετερμινιστικό.
Στο παρακάτω διάγραμμα το αυτόματα στοίβας παράγει τη γλώσσα L όπου:
L = {0n1n | n ≥ 0}
Στο παρακάτω διάγραμμα που το αυτόματα στοίβας παράγει τη γλώσσα L όπου:
L = {0n1n | n ≥ 0}
ελέγχεται η συμβολοσειρά 0011
.
Για να είναι αποδεκτή μια συμβολοσειρά θα πρέπει να ισχύουν και τα δύο παρακάτω:
- Να καταλήγει σε τελική κατάσταση
- Η στοίβα να είναι άδεια
Στο παρακάτω διάγραμμα το αυτόματα στοίβας παράγει τη γλώσσα L όπου:
L = {wwR | w = (a+b)+}
Σύμφωνα με τον ορισμό οι λέξεις είναι παλίνδρομα της μορφής wwR. Για παράδειγμα: abccba, 110011 κλπ.
Για το παραπάνω παράδειγμα να δείξετε ότι το παλίνδρομο abba είναι αποδεκτό ενώ η συμβολοσειρά abab δεν είναι.
Να δείξετε επίσης πως αλλάζει η στοίβα.