Ποιο είναι το παράδειγμα μιας αποφασιστικής γλώσσας;

Εδώ είναι γιατί είναι αποφασιστικό και πώς μπορεί να το αποφασίσει μια μηχανή Turing:

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

μηχάνημα Turing Decider: Μπορούμε να κατασκευάσουμε ένα μηχάνημα Turing `d` που αποφασίζει` a` ως εξής:

1. είσοδος: `D` παίρνει ως εισροή` `, όπου` m` είναι η κωδικοποίηση ενός DFA και `w` είναι μια συμβολοσειρά.

2. Προσομοίωση: `D` προσομοιώνει το dfa` m` σε συμβολοσειρά εισόδου `w`. Αυτό είναι δυνατό επειδή `d` μπορεί να παρακολουθεί την τρέχουσα κατάσταση του` m` και το τρέχον σύμβολο που διαβάζεται από το `w`. Η προσομοίωση προχωρά ως εξής:

* Ξεκινήστε `m` στην αρχική του κατάσταση.

* Για κάθε σύμβολο στο `w`, μετάβαση` m` στην επόμενη κατάσταση ανάλογα με τη λειτουργία μετάβασης.

3. Αποδοχή/απόρριψη:

* Εάν το `m` τελειώνει σε μια κατάσταση αποδοχής μετά την ανάγνωση ολόκληρης της συμβολοσειράς` w`, τότε `d` δέχεται` `.

* Εάν το "m` τελειώνει σε κατάσταση μη αποδόσεως μετά την ανάγνωση ολόκληρης της συμβολοσειράς` w`, τότε `d` απορρίπτει` `.

Γιατί αυτό λειτουργεί:

* DFAS πάντα σταματά: Τα DFA, εξ ορισμού, επεξεργάζονται κάθε σύμβολο εισόδου ακριβώς μία φορά και στη συνέχεια σταματήστε. Δεν έχουν άπειρους βρόχους ή απροσδιόριστη συμπεριφορά.

* Η προσομοίωση είναι δυνατή: Μια μηχανή Turing μπορεί εύκολα να προσομοιώσει την ντετερμινιστική συμπεριφορά ενός DFA επειδή έχει αρκετή μνήμη και έλεγχο για να παρακολουθεί την κατάσταση και τη θέση εισόδου του DFA.

* σταματήστε: Το μηχάνημα Turing `D` σταματά πάντα επειδή η προσομοίωση DFA σταματά πάντα.

* ορθότητα: `D` δέχεται ακριβώς τις χορδές` `όπου` m` δέχεται `w 'και απορρίπτει ακριβώς τις χορδές` `όπου` m` δεν * δεν δέχεται `w`.

επίσημη απόδειξη (σκίτσο):

Για να αποδείξετε αυστηρά την ευελιξία, θα χρειαστεί να:

1. Καθορίστε τυπικά την κωδικοποίηση: Καθορίστε πώς ένα DFA `m` και μια συμβολοσειρά` w` αντιπροσωπεύονται ως χορδές στο αλφάβητο εισόδου του μηχανήματος Turing 'd`.

2. Καθορίστε τυπικά το μηχάνημα Turing `d`: Δώστε ένα διάγραμμα κατάστασης ή μια επίσημη περιγραφή των μεταβάσεων του «d».

3. Αποδείξτε τη ορθότητα: Δείξτε ότι αν το `` είναι στη γλώσσα `a`, τότε` d` το δέχεται, και αν `` δεν είναι * στη γλώσσα `a`, τότε` d` απορρίπτεται.

4. Αποδείξτε σταμάτησε: Δείξτε ότι το "D` σταματά πάντα σε οποιαδήποτε είσοδο.

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