Αυτόματα στοίβας

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

Τα αυτόματα στοίβας (ΑΣ) ορίζονται από την εξάδα Μ = (Κ, Σ, Γ, δ, q₀, Z₀)

K: Πεπερασμένο σύνολο καταστάσεων
Σ: Αλφάβητο εισόδου
Γ: Αλφάβητο για τη στοίβα
δ: Σύνολο κινήσεων που εκτελεί το αυτόματο
q₀: Αρχική κατάσταση
Ζ₀: Αρχική σύμβολο της στοίβας

Κάθε εντολή του ΑΣ ονομάζεται κίνηση (move). Η κίνηση ορίζεται από:

την κατάσταση του ΑΣ,
το σύμβολο στην κορυφή της στοίβας,
το σύμβολο εισόδου.

Όταν σε κάθε τριάδα αντιστοιχεί μια το πολύ κίνηση τότε το αυτόματο λέγεται ντετερμινιστικό αυτόματο στοίβας (ΝΑΣ) (deterministic stack automaton (DSA)). Αντίθετα, αν για κάποιες τιμές της δ υπάρχουν πολλές πιθανές κινήσεις τότε το αυτόματο καλείται μη ντετερμινιστικό αυτόματο στοίβας (ΜΑΣ) (non-deterministic stack automaton (NSA)). (Οι λέξη ντετερμινιστικό που εμφανίζεται στην ελληνική βιβλιογραφία είναι συνώνυμη με τη λέξη αιτιοκρατικό).

Η λειτουργία του ΑΣ ορίζεται από τρεις υποεντολές που εκτελούνται διαδοχικά:

την υποεντολή της στοίβας
την υποεντολή εισόδου
την υποεντολή επόμενης κατάστασης

Οι εντολές μπορούν να εκτελέσουν τις παρακάτω λειτουργίες:

υποεντολή της στοίβας

ΒΑΛΕ(χ)
το χ προστίθεται στη στοίβα
ΒΓΑΛΕ
ένα στοιχείο αφαιρείται από τη στοίβα
ΑΦΗΣΕ
η στοίβα δε μεταβάλλεται
υποεντολή εισόδου

ΠΡΟΧΩΡΑ
διάβασε ένα νέο στοιχείο από την είσοδο
ΚΡΑΤΑ
κράτα το υπάρχον στοιχείο εισόδου
υποεντολή επόμενης κατάστασης

ΚΑΤΑΣΤΑΣΗ(S)
η νέα κατάσταση είναι η S