Αυτόματα στοίβας (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

Σχηματική αναπαράσταση

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

pushdown-automata

Η έκφραση b→c δείχνει ότι το b πρέπει να γίνει pop και το c να γίνει push.

Αν b = ε δεν έχουμε pop όπως επίσης αν c = ε δεν έχουμε push.

Μπορεί επίσης να ισχύει a = ε αφού το αυτόματο στοίβας δεν είναι ντετερμινιστικό.

Στο παρακάτω διάγραμμα το αυτόματα στοίβας παράγει τη γλώσσα L όπου:

L = {0n1n | n ≥ 0}

pushdown-automata

Στο παρακάτω διάγραμμα που το αυτόματα στοίβας παράγει τη γλώσσα L όπου:

L = {0n1n | n ≥ 0}

ελέγχεται η συμβολοσειρά 0011.

pushdown-automata

Για να είναι αποδεκτή μια συμβολοσειρά θα πρέπει να ισχύουν και τα δύο παρακάτω:

  1. Να καταλήγει σε τελική κατάσταση
  2. Η στοίβα να είναι άδεια

Στο παρακάτω διάγραμμα το αυτόματα στοίβας παράγει τη γλώσσα L όπου:

L = {wwR | w = (a+b)+}

Σύμφωνα με τον ορισμό οι λέξεις είναι παλίνδρομα της μορφής wwR. Για παράδειγμα: abccba, 110011 κλπ.

pushdown-automata

Για το παραπάνω παράδειγμα να δείξετε ότι το παλίνδρομο abba είναι αποδεκτό ενώ η συμβολοσειρά abab δεν είναι.

Να δείξετε επίσης πως αλλάζει η στοίβα.