1. Σταματά σε όλες τις εισόδους: Το TM πρέπει τελικά να φτάσει είτε σε κατάσταση αποδοχής είτε σε κατάσταση απόρριψης, ανεξάρτητα από τη συμβολοσειρά εισόδου. Δεν μπορεί να βρόχο για πάντα.
2. δέχεται χορδές στη γλώσσα l: Εάν μια συμβολοσειρά `w` είναι στο L, το TM σταματά σε κατάσταση αποδοχής.
3. Απορρίπτει τις χορδές όχι στη γλώσσα l: Εάν μια συμβολοσειρά `w` δεν είναι στο L, το TM σταματά σε κατάσταση απόρριψης.
Με άλλα λόγια, μια αποφασιστική γλώσσα έχει μια μηχανή Turing που λειτουργεί ως τέλειος δοκιμαστής μέλους:δίνει πάντα μια απάντηση "ναι" ή "όχι" και πάντα το κάνει σε πεπερασμένο χρονικό διάστημα.
Ακολουθεί μια κατανομή κοινών τεχνικών και εκτιμήσεων:
1. Κατασκευή μιας μηχανής Turing (TM) Περιγραφή:
* Περιγραφή υψηλού επιπέδου: Ξεκινήστε με μια σαφή, ανθρώπινη αναγνώσιμη περιγραφή του αλγορίθμου του TM. Αυτό θα πρέπει να εξηγήσει τη λογική και τα βήματα που χρειάζεται για την επεξεργασία της εισόδου. Σκεφτείτε το ως ψευδο-κώδικα.
* Περιγραφή σε επίπεδο υλοποίησης (προαιρετικό): Μπορείτε * μπορείτε να παρέχετε μια περιγραφή χαμηλότερου επιπέδου, καθορίζοντας τις καταστάσεις, τη λειτουργία μετάβασης, το αλφάβητο ταινίας κλπ. Αυτό είναι συχνά κουραστικό και δεν απαιτείται εκτός αν ζητηθεί ρητά ή εάν ο αλγόριθμος είναι πολύ λεπτός και απαιτεί ακριβή ορισμό. Εστίαση στην περιγραφή υψηλού επιπέδου πρώτα.
* Η σαφήνεια είναι το κλειδί: Το πιο σημαντικό είναι ότι η περιγραφή σας είναι κατανοητή και πειστική. Μια κακή γραπτή περιγραφή υψηλού επιπέδου μπορεί να είναι πιο δύσκολο να κατανοηθεί από μια καλά γραπτή επίσημη περιγραφή.
2. Γενικές στρατηγικές για το σχεδιασμό των αποφασιστικών μέσων:
* Προσομοίωση άλλων μηχανών: Εάν μπορείτε να δείξετε ότι το L μπορεί να αποφασιστεί με προσομοίωση μιας άλλης αποφασιστικής γλώσσας (ή πολλαπλών τέτοιων γλωσσών), έχετε δείξει ότι το L είναι αποφασιστικό. Η παραφροσύνη είναι κλειστή κάτω από πολλές επιχειρήσεις (ένωση, διασταύρωση, συμπλήρωμα, συγκόλληση, αστέρι Kleene).
* Μετατροπή σε ένα απλούστερο πρόβλημα: Προσπαθήστε να επανατοποθετήσετε το πρόβλημα σε ένα ισοδύναμο αλλά ευκολότερο να επιλυθείτε πρόβλημα.
* Εξετάστε τις βασικές περιπτώσεις και επανάληψη: Εάν το πρόβλημα έχει μια αναδρομική δομή, ένας αναδρομικός αλγόριθμος μπορεί να μεταφραστεί σε ένα μηχάνημα Turing. Βεβαιωθείτε ότι η επανάληψη είναι περιορισμένη για να εγγυηθεί τον τερματισμό.
* Εξαντλητική αναζήτηση: Εάν ο χώρος εισόδου είναι πεπερασμένος ή μπορεί να οριοθετηθεί, μπορείτε συχνά να χρησιμοποιήσετε εξαντλητική αναζήτηση για να ελέγξετε όλες τις δυνατότητες. Το κρίσιμο σημείο είναι ότι η αναζήτηση πρέπει να είναι εγγυημένη για να τερματιστεί.
* Αξιοποιήστε γνωστές αναγνωρίσιμες γλώσσες: Βασιστείτε στη γνώση ότι ορισμένες γλώσσες είναι ήδη αποφασιστικές. Για παράδειγμα, κανονικές γλώσσες, γλώσσες χωρίς περιβάλλοντα και πολλά άλλα.
3. Τεχνικές για την επίδειξη τερματισμού:
* Καταμέτρηση: Δείξτε ότι ο αλγόριθμος περιλαμβάνει έναν μετρητή που αυξάνεται αυστηρά ή μειώνεται προς ένα όριο.
* μείωση του μεγέθους: Δείξτε ότι κάθε βήμα του αλγορίθμου μειώνει το μέγεθος του προβλήματος μέχρι να φτάσει σε μια ασήμαντη περίπτωση βάσης.
* Δεν υπάρχουν άπειροι βρόχοι: Υποστηρίζει πειστικά ότι ο αλγόριθμος δεν μπορεί να εισέλθει σε άπειρο βρόχο. Αυτό μπορεί να περιλαμβάνει την εμφάνιση ότι το μηχάνημα μετακινεί πάντα την κεφαλή της ταινίας ή ότι τα κράτη που επισκέπτονται είναι πάντα διακριτά μέσα σε μια συγκεκριμένη περίοδο.
* Μήκος προσομοίωσης: Εάν ο αλγόριθμος προσομοιώνει ένα άλλο TM, δημιουργήστε ένα ανώτερο όριο στον αριθμό των βημάτων που θα λάβει η προσομοίωση. Αυτό συχνά εξαρτάται από το μέγεθος της εισόδου.
4. Παραδείγματα και κοινά σενάρια:
* Τακτικές γλώσσες: Για να δείξετε μια κανονική γλώσσα είναι αποφασιστική, παρέχετε ένα DFA για τη γλώσσα. Ένα TM μπορεί να προσομοιώσει το DFA και να σταματήσει σε κατάσταση αποδοχής ή απόρριψης βάσει της τελικής κατάστασης του DFA.
* Γλώσσες χωρίς περιβάλλον: Χρησιμοποιήστε τον αλγόριθμο Cyk ή έναν παρόμοιο αλγόριθμο ανάλυσης. Αυτοί οι αλγόριθμοι έχουν πεπερασμένο χρόνο εκτέλεσης.
* Ανεξάρτητα: Κατανοήστε το πρόβλημα διακοπής. Δεν μπορείτε να αποφασίσετε εάν μια αυθαίρετη μηχανή Turing σταματά σε μια αυθαίρετη είσοδο. Εάν μπορείτε να μειώσετε το πρόβλημα διακοπής στο πρόβλημά σας, έχετε δείξει ότι το πρόβλημά σας είναι αδιαμφισβήτητο (όχι αποφασιστικό).
* Δοκιμές κενότητας: Η εμφάνιση μιας γλώσσας είναι * κενή * (δεν περιέχει χορδές) είναι μερικές φορές ευκολότερη από την εμφάνιση του αποφασιστικού. Για παράδειγμα, η γλώσσα ενός μηχανήματος Turing είναι * δεν είναι * αποφασιστική. Ωστόσο, δεδομένου ενός DFA ή CFG, καθορίζοντας εάν η γλώσσα που αντιπροσωπεύει είναι κενή * είναι * αποφασιστική.
5. Τι να μην κάνω:
* Μην ισχυρίζεστε ότι είναι αποφασιστικό χωρίς δικαιολογία. Πρέπει να παράσχετε ένα λογικό επιχείρημα, το οποίο συνήθως σημαίνει περιγραφή του αλγορίθμου.
* Μην παρέχετε ένα TM που * μόνο * δέχεται χορδές στη γλώσσα. Πρέπει επίσης να απορρίψει * χορδές * όχι * στη γλώσσα και πρέπει να σταματήσει.
* Μην παρέχετε έναν αλγόριθμο που * μπορεί να σταματήσει, αλλά έχει τη δυνατότητα να βρόχο για πάντα. Ένας αποφασιστής * πρέπει να σταματήσει.
* Μην συγχέετε την παραφροσυσότητα με την αναγνώριση. Μια αναγνωρίσιμη γλώσσα απαιτεί μόνο ένα TM να σταματήσει και να αποδεχθεί εάν η είσοδος είναι στη γλώσσα. Μπορεί να βρόχο για πάντα εάν η είσοδος δεν είναι στη γλώσσα. Οι δεκτές γλώσσες είναι πάντα αναγνωρίσιμες, αλλά το αντίστροφο δεν είναι αλήθεια.
* Μην προσπαθήσετε να δώσετε μια "απόδειξη από παράδειγμα" Η εμφάνιση ότι μια συγκεκριμένη είσοδος γίνεται αποδεκτή ή απορρίφθηκε δεν αποδεικνύει τίποτα για την παραφροσύνη της γλώσσας.
Παράδειγμα 1:a ={0
* Περιγραφή υψηλού επιπέδου:
1. Σάρωση της συμβολοσειρά εισόδου για να βεβαιωθείτε ότι αποτελείται μόνο από 0s που ακολουθείται από 1s. Εάν όχι, απορρίψτε.
2. Ενώ υπάρχουν και τα δύο και τα 1s:
* Διασταύρωση από το αριστερό 0.
* Διακόσμηση από το αριστερό 1.
3. Εάν δεν παραμένουν οι 0s και το 1, αποδεχτείτε.
4. Εάν παραμένουν μόνο 0s ή μόνο 1s, απορρίψτε.
* Αιτιολόγηση: Αυτός ο αλγόριθμος σταματά για όλες τις εισόδους. Τα βήματα 1 και 3/4 τερματίζουν τους ελέγχους. Το βήμα 2 διασχίζει ένα 0 και ένα 1 σε κάθε επανάληψη. Ο αριθμός των 0s και 1s είναι πεπερασμένος, οπότε ο βρόχος θα τερματιστεί. Εάν ο αριθμός των 0s και 1s ήταν ίσος, δεχόμαστε. Διαφορετικά, απορρίπτουμε.
Παράδειγμα 2:Δεδομένου ενός dfa d, είναι η γλώσσα του l (d) κενή; Ένα
* Περιγραφή υψηλού επιπέδου:
1. Σημειώστε την κατάσταση εκκίνησης του Δ.
2. Επαναλάβετε μέχρι να σημειωθούν νέα κράτη:
* Σημειώστε κάθε κατάσταση που μπορεί να προσεγγιστεί από μια επί του παρόντος σημειωμένη κατάσταση ακολουθώντας ένα βέλος στο Δ.
3. Εάν έχει επισημανθεί οποιαδήποτε αποδοχή της κατάστασης D, απορρίπτεται.
4. Διαφορετικά, αποδεχτείτε.
* Αιτιολόγηση: Αυτός ο αλγόριθμος σταματά. Το βήμα 2 διερευνά όλες τις πιθανές προσβάσιμες καταστάσεις. Ο αριθμός των κρατών στο D είναι πεπερασμένος, οπότε ο βρόχος θα τερματιστεί. Εάν μπορούμε να φτάσουμε σε μια κατάσταση αποδοχής, η γλώσσα δεν είναι κενή και απορρίπτουμε. Διαφορετικά, είναι και δεχόμαστε. Σημειώστε ότι το «D» είναι εγγυημένο ότι είναι DFA με υπόθεση και έτσι έχει πεπερασμένες καταστάσεις.
Ακολουθώντας αυτές τις στρατηγικές και την κατανόηση των ιδιοτήτων των μηχανών Turing και των αποφασιστικών γλωσσών, μπορείτε να αποδείξετε αποτελεσματικά ότι μια γλώσσα είναι αποφασιστική. Θυμηθείτε να επικεντρωθείτε σε μια σαφή και πειστική περιγραφή αλγορίθμου και ένα υγιές επιχείρημα για τον τερματισμό και την ορθότητα του.
Πνευματικά δικαιώματα © Γνώση Υπολογιστών Όλα τα δικαιώματα κατοχυρωμένα