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

Για να αποδειχθεί μια γλώσσα L είναι αποφασιστική, πρέπει να δείξετε ότι υπάρχει μια μηχανή Turing (ή ένα ισοδύναμο υπολογιστικό μοντέλο) που σταματά και δέχεται χορδές σε L και απορρίπτει συμβολοσειρές όχι στο L. Υπάρχουν διάφοροι τρόποι για να αποδείξετε αυτό:

1. Κατασκευή μηχανής Turing (ή αλγόριθμος):

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

* είσοδος: Πώς το μηχάνημα Turing λαμβάνει τη συμβολοσειρά εισόδου.

* κράτη: Τις διαφορετικές καταστάσεις που μπορεί να είναι το μηχάνημα.

* Μεταβάσεις: Πώς μετακινείται το μηχάνημα μεταξύ των καταστάσεων με βάση την τρέχουσα κατάσταση και το σύμβολο που διαβάζεται από την ταινία.

* Αποδοχή/απόρριψη: Πώς το μηχάνημα σηματοδοτεί την αποδοχή (π.χ., εισάγοντας μια κατάσταση "αποδοχής") ή απόρριψη (π.χ., εισάγοντας μια κατάσταση "απορρίψεων").

* σταματήστε: Βασικά, πρέπει να αποδείξετε ότι το μηχάνημα * πάντα * σταματά, ανεξάρτητα από το αν η συμβολοσειρά εισόδου είναι σε L ή όχι. Αυτό είναι το πιο δύσκολο κομμάτι.

Παράδειγμα: Εξετάστε τη γλώσσα l ={w | Το W είναι ένα palindrome}. Μπορούμε να περιγράψουμε μια μηχανή Turing που:

1. Σαρώνει την ταινία εισόδου από αριστερά προς τα δεξιά, σημειώνοντας τα πρώτα και τα τελευταία σύμβολα.

2. Μετακινεί τους δείκτες ένα βήμα προς τα μέσα και από τα δύο άκρα.

3. Επαναλαμβάνει το βήμα 2 μέχρι να συναντηθούν οι δείκτες (η συμβολοσειρά είναι ένα palindrome) ή οι δείκτες σταυροειδείς (η συμβολοσειρά δεν είναι palindrome).

4 αποδέχεται εάν οι δείκτες συναντιούνται και απορρίπτουν εάν διασχίσουν.

Αυτό το μηχάνημα σταματά πάντα, αποδεικνύοντας ότι το L είναι αποφασιστικό.

2. Μείωση σε μια γνωστή αποφασιστική γλώσσα:

Εάν μπορείτε να δείξετε ότι η γλώσσα σας μπορεί να μειωθεί σε μια γνωστή αποφασιστική γλώσσα L ', αυτό αποδεικνύει ότι το L είναι επίσης αποφασιστικό. Η μείωση είναι μια υπολογιστική συνάρτηση f έτσι ώστε:

* x ∈ L αν και μόνο αν f (x) ∈ L '

Εάν έχετε έναν αλγόριθμο για να αποφασίσετε L ', μπορείτε να το χρησιμοποιήσετε για να αποφασίσετε L εφαρμόζοντας πρώτα τη μείωση. Δεδομένου ότι τόσο το F όσο και ο αλγόριθμος για L 'είναι υπολογιστές, η συνδυασμένη διαδικασία είναι επίσης υπολογιστική, αποφασίζοντας έτσι L.

Παράδειγμα: Αφήστε το L να είναι η γλώσσα των χορδών που αντιπροσωπεύουν έγκυρες αριθμητικές εκφράσεις. Μπορούμε να μειώσουμε το L σε μια γλώσσα Grammar (CFG) L ', η οποία είναι αποφασιστική (υπάρχουν αλγόριθμοι ανάλυσης για CFGs). Η μείωση θα συνεπάγεται τη μετατροπή της σειράς αριθμητικής έκφρασης σε ένα δέντρο ανάλυσης σύμφωνα με τη γραμματική. Εάν ο μετασχηματισμός πετύχει και δημιουργείται ένα έγκυρο δέντρο αναλύσεων, η συμβολοσειρά είναι στο L Διαφορετικά, δεν είναι.

3. Χρήση ιδιοτήτων κλεισίματος των δεκτών γλωσσών:

Οι δεκτές γλώσσες κλείνουν κάτω από ορισμένες πράξεις όπως η Ένωση, η Διασύνδεση, η Συνέλευση, η Κλενική Αστέρα και το Συμπλήρωμα. Εάν μπορείτε να εκφράσετε τη γλώσσα σας χρησιμοποιώντας αυτές τις λειτουργίες σε γνωστές δεκτές γλώσσες, τότε το L είναι επίσης αποφασιστικό.

Παράδειγμα: Εάν τα L1 και L2 είναι αποφασιστικά, τότε το L1 ∪ L2 είναι επίσης αποφασιστικό. Μπορείτε να αποφασίσετε L1 ∪ L2 εκτελώντας τους αλγόριθμους απόφασης για L1 και L2 στη συμβολοσειρά εισόδου. Εάν είτε αποδέχεται, η Ένωση αποδέχεται.

Συνοπτικά: Η απόδειξη του Decidability βράζει κάτω για να δείξει ότι υπάρχει ένας ντετερμινιστικός αλγόριθμος (ή η μηχανή Turing) που θα σταματήσει πάντα και θα ταξινομήσει σωστά κάθε συμβολοσειρά εισόδου ως ανήκει στη γλώσσα ή όχι. Η μέθοδος που επιλέγετε εξαρτάται από τη συγκεκριμένη γλώσσα και τη διαίσθησή σας σχετικά με τις ιδιότητές της. Η πιο συνηθισμένη προσέγγιση είναι η άμεση κατασκευή ενός μηχανήματος ή αλγόριθμου Turing, αλλά οι μειώσεις και οι ιδιότητες κλεισίματος είναι ισχυρά εργαλεία για πιο σύνθετες γλώσσες.