Ποια γλώσσα γίνεται αποδεκτή από το PDA για είσοδο και επεξεργασία;

Το Automaton (PDA) αποδέχεται μια γλώσσα που είναι μια γλώσσα χωρίς περιεχόμενο (CFL) .

Εδώ είναι γιατί:

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

* ισοδυναμία με γραμματικές χωρίς περιβάλλοντα: Τα PDA είναι ισοδύναμα στην εξουσία σε γραμματικές χωρίς περιβάλλοντα. Αυτό σημαίνει ότι:

* Για κάθε CFL, μπορείτε να σχεδιάσετε ένα PDA που το δέχεται.

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

* Περιορισμοί: Τα PDA δεν μπορούν να αναγνωρίσουν όλες τις γλώσσες. Δεν μπορούν * να αναγνωρίσουν τις γλώσσες που απαιτούν πιο σύνθετες δυνατότητες μνήμης ή υπολογιστικών δυνατοτήτων πέρα ​​από τη στοίβα, όπως οι ευαίσθητες στο περιβάλλον γλώσσες (που θα απαιτούσαν κάτι πιο ισχυρό όπως ένα μηχάνημα Turing).