Ποιες είναι οι ιδιότητες κλεισίματος των δεκτών γλωσσών;

Οι δεκτές γλώσσες είναι κλειστές κάτω από τις ακόλουθες εργασίες:

1. Ένωση: Εάν τα L1 και L2 είναι αποφασιστικές γλώσσες, τότε το L1 ∪ L2 είναι επίσης αποφασιστικό.

* Επεξήγηση: Μπορούμε να κατασκευάσουμε μια μηχανή Turing (TM) που αποφασίζει L1 ∪ L2. Το TM, στην είσοδο 'W', προσομοιώνει τα TMS για L1 και L2 σε σειρά.

* Πρώτον, προσομοιώστε το TM για L1. Εάν δέχεται, τότε δεχτείτε το 'W'.

* Εάν το TM για L1 απορρίπτεται, τότε προσομοιώστε το TM για L2. Εάν δέχεται, τότε δεχτείτε το 'W'.

* Εάν το TM για L2 απορρίπτει, απορρίψτε τότε το 'W'.

* Βασικό σημείο: Δεδομένου ότι τα L1 και L2 είναι αποφασιστικά, το αντίστοιχο TMS * πάντα * σταματάει (είτε αποδοχή είτε απόρριψη). Αυτό εξασφαλίζει ότι το TM που καθορίζει την ένωση επίσης σταματά πάντα.

2. Διασταύρωση: Εάν τα L1 και L2 είναι αποφασιστικές γλώσσες, τότε το L1 ∩ L2 είναι επίσης αποφασιστικό.

* Επεξήγηση: Παρόμοια με την ένωση, μπορούμε να οικοδομήσουμε ένα TM που αποφασίζει L1 ∩ L2.

* Προσομοίωση του TM για L1. Εάν απορρίψει, απορρίψτε τότε το 'W'.

* Εάν το TM για L1 δέχεται, τότε προσομοιώστε το TM για L2. Εάν δέχεται, τότε δεχτείτε το 'W'.

* Εάν το TM για L2 απορρίπτει, απορρίψτε τότε το 'W'.

3. Συμπλήρωμα: Εάν το L είναι μια αποφασιστική γλώσσα, τότε το L '(το συμπλήρωμα του L) είναι επίσης αποφασιστικό.

* Επεξήγηση: Μπορούμε να κατασκευάσουμε ένα TM για το L 'απλά ανταλλάσσοντας τις αποδοχές και απορρίπτοντας τις καταστάσεις του TM που αποφασίζουν L.

* Λαμβάνοντας υπόψη το TM για L, δημιουργήστε ένα νέο TM που είναι πανομοιότυπο εκτός από:Εάν το αρχικό TM αποδέχεται, το νέο TM απορρίπτει. Εάν το αρχικό TM απορρίπτεται, το νέο TM δέχεται.

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

4. Συμπύκνωση: Εάν τα L1 και L2 είναι αναγνωρίσιμες γλώσσες, τότε η L1L2 (η συγκόλληση των L1 και L2) είναι επίσης αποφασιστική.

* Επεξήγηση:

* Στην είσοδο `w`, δοκιμάστε όλους τους δυνατούς τρόπους για να χωρίσετε` w` σε δύο μέρη, `x` και` y`, έτσι ώστε `w =xy`.

* Για κάθε διάσπαση, προσομοιώστε το TM για το L1 στο `x` και το TM για το L2 στο` Y '.

* Εάν το TM για το L1 δέχεται `x` * και * Το TM για το L2 δέχεται` y`, τότε αποδέχονται `w`.

* Εάν έχουν δοκιμαστεί όλες οι πιθανές διαχωρισμούς και κανένας δεν ικανοποιεί την παραπάνω κατάσταση, τότε απορρίψτε το «w».

* ΣΗΜΑΝΤΙΚΟ: Δεδομένου ότι τα L1 και L2 είναι αποδεκτά, αυτές οι προσομοιώσεις σταματούν πάντα. Επειδή δοκιμάζουμε όλες τις πιθανές διαχωρισμούς, το συνολικό TM σταματά πάντα.

5. Kleene Star: Εάν το L είναι μια αποφασιστική γλώσσα, τότε ο L* (το αστέρι Kleene του L) είναι επίσης αποφασιστικό.

* Επεξήγηση: Αυτό είναι παρόμοιο με τη συγκόλληση, αλλά επιτρέπουμε πολλαπλές συνολικές (συμπεριλαμβανομένου του μηδέν).

* Στην είσοδο `w`, για` i =0` to `| w |`:(όπου `| w |` είναι το μήκος του `w`)

* Δοκιμάστε όλους τους δυνατούς τρόπους για να χωρίσετε `w` σε` I 'μέρη, `x1, x2, ..., xi`, έτσι ώστε` w =x1x2 ... xi`.

* Για κάθε διάσπαση, προσομοιώστε το TM για L σε κάθε `xj`.

* Εάν το TM για L δέχεται κάθε `xj` (για όλα` j` από 1 έως `i '), τότε δεχτείτε` w'.

* Εάν όλες οι πιθανές τιμές του «I 'και όλες οι πιθανές διαχωρισμούς έχουν δοκιμαστεί και κανένας δεν ικανοποιεί την παραπάνω κατάσταση, τότε απορρίψτε το« w ».

* Βασική διορατικότητα: Δεδομένου ότι το μήκος οποιασδήποτε συμβολοσειράς στο L* δεν μπορεί να είναι μεγαλύτερο από το μήκος της εισόδου `w`, μπορούμε να περιορίσουμε τον αριθμό των διαχωρισμών που πρέπει να δοκιμάσουμε. Η προσομοίωση σταματά αφού εξετάζει όλες τις πιθανές διαχωρισμούς.

6. Αντιστροφή: Εάν το L είναι μια αποφασιστική γλώσσα, τότε l r (Η αναστροφή του L) είναι επίσης αποφασιστική.

* Επεξήγηση: Κατασκευάστε ένα TM που κάνει τα εξής:

* Αντιστρέψτε τη συμβολοσειρά εισόδου `w` για να πάρετε` w r `.

* Προσομοίωση του TM για L στο `W r `.

* Εάν το TM για L δέχεται `w r `, τότε δεχτείτε` w`. Διαφορετικά, απορρίψτε το `w`.

7. Διαφορά: Εάν τα L1 και L2 είναι αποφασιστικές γλώσσες, τότε το L1 -L2 είναι επίσης αποφασιστικό. (L1 - L2 περιέχει όλες τις χορδές στο L1 που δεν είναι * στο L2).

* Επεξήγηση: L1 - L2 =L1 ∩ L2 '. Δεδομένου ότι οι δεκτές γλώσσες είναι κλειστές υπό συμπλήρωση και διασταύρωση, είναι επίσης κλειστές υπό διαφορά.

8. Πρόθεμα: Εάν το L είναι μια αποφασιστική γλώσσα, τότε το πρόθεμα (l) ={x | Για μερικά y, το xy ∈ L} είναι αποφασιστικό.

* Επεξήγηση:

* Στην είσοδο `x`, για όλα τα δυνατά` y` έτσι ώστε `| xy | <=| x | + some_constant`, (όπου `some_constant` είναι το μέγιστο μήκος των χορδών για δοκιμή),

* Προσομοίωση του TM για L στο `xy '

* Εάν το TM αποδέχεται, αποδεχτείτε το «x»

* Απορρίψτε εάν δεν αποδέχεται καμία από τις παραπάνω προσομοιώσεις.

Γιατί το κλείσιμο είναι σημαντικό;

Οι ιδιότητες κλεισίματος είναι θεμελιώδεις για την κατανόηση της εξουσίας και των περιορισμών των επίσημων τάξεων γλώσσας. Η γνώση ότι μια τάξη γλωσσών είναι κλειστή κάτω από ορισμένες λειτουργίες μας επιτρέπει να:

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

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

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

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

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