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

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

1. Παρέχετε μια γραμματική χωρίς περιβάλλοντα (CFG):

* Η πιο άμεση και συχνά χρησιμοποιούμενη μέθοδος. Εάν μπορείτε να σχεδιάσετε ένα CFG που παράγει * ακριβώς * τις χορδές στη γλώσσα, έχετε αποδείξει ότι είναι χωρίς περιεχόμενο.

* Ορισμός CFG: Ένα CFG αποτελείται από:

* * Μη τερματικά (μεταβλητές):* που αντιπροσωπεύονται από κεφαλαία γράμματα (π.χ., `s`,` a`, `b`).

* * Τερματικά:* Τα σύμβολα αλφάβητου της γλώσσας (π.χ., `a`,` b`, `0`,` 1`).

* * Σύμβολο εκκίνησης:* Ένα διακεκριμένο μη τερματικό (συνήθως `s`).

* * Κανόνες παραγωγής:* Κανόνες της φόρμας «μη τερματικό -> string των τερματικών και/ή μη τερματικών» (π.χ., S -> ASB | ε `).

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

* Παράδειγμα:

* Γλώσσα:l ={a n B n | n ≥ 0} (χορδές με ίσους αριθμούς 'a και' b, με αυτή τη σειρά)

* CFG:

* `S -> asb | ε "(όπου ε αντιπροσωπεύει την κενή συμβολοσειρά)

* Επεξήγηση:

* `S` δημιουργεί το βασικό μοτίβο` ASB`.

* Με την αναδρομική εφαρμογή του κανόνα `s -> asb`, μπορείτε να δημιουργήσετε οποιοδήποτε αριθμό` a 'και `b είναι, εξασφαλίζοντας ότι είναι ισορροπημένες.

* Ο κανόνας `s -> ε` σάς επιτρέπει να τερματίσετε την επανάληψη και να παράγετε την κενή συμβολοσειρά (η οποία είναι επίσης στη γλώσσα όταν n =0).

2. Παρέχετε ένα automaton pushdown (PDA):

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

* Ορισμός PDA: Ένα PDA είναι ένα πεπερασμένο αυτόματο με στοίβα. Μπορεί να διαβάσει σύμβολα εισόδου, να αλλάξει την κατάστασή του και να πιέζει ή να ποπ σύμβολα από τη στοίβα.

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

* Παράδειγμα (για την ίδια γλώσσα l ={a n B n | n ≥ 0}):

* Το PDA διαβάζει 'Α και τους ωθεί στη στοίβα.

* Όταν συναντά ένα «Β», σκάει ένα «Α» από τη στοίβα.

* Το PDA δέχεται εάν έχει διαβάσει όλες τις εισροές και η στοίβα είναι κενή.

* ΣΗΜΑΝΤΙΚΟ: Καθορίστε τον τρόπο με τον οποίο μεταβαίνει το PDA μεταξύ των καταστάσεων με βάση τα σύμβολα εισόδου και το περιεχόμενο στοίβας.

3. Χρησιμοποιήστε ιδιότητες κλεισίματος:

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

* Ιδιότητες κλεισίματος:

* Ένωση: Εάν τα L1 και L2 είναι απαλλαγμένα από το περιβάλλον, τότε το L1 ∪ L2 είναι απαλλαγμένο από το περιβάλλον.

* Συνέλευση: Εάν τα L1 και L2 είναι απαλλαγμένα από το περιβάλλον, τότε το L1L2 είναι απαλλαγμένο από το περιβάλλον.

* Kleene Star ( *): Εάν το L είναι απαλλαγμένο από το περιβάλλον, τότε το L* είναι απαλλαγμένο από το περιβάλλον.

* Ομομορφισμός: Εάν το L είναι χωρίς περιβάλλον και το `h` είναι ομομορφισμός (μια συνάρτηση που χαρτογραφεί τα σύμβολα σε χορδές), τότε` h (l) `είναι χωρίς περιβάλλον.

* Αντίστροφη ομομορφισμός: Εάν το L είναι χωρίς περιεχόμενο και το `h` είναι ομομορφισμός, τότε` h -1 (L) `είναι χωρίς περιβάλλοντα. (Ο αντίστροφος ομομορφισμός παίρνει μια συμβολοσειρά ως είσοδο και επιστρέφει το σύνολο των χορδών που, όταν εφαρμόζεται ο ομομορφισμός, σας δίνει τη συμβολοσειρά εισόδου).

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

* Παράδειγμα:

* Δείξτε ότι l ={a n B n c m d m | n, m ≥ 0} είναι χωρίς περιβάλλον.

* L1 ={a n B n | n ≥ 0} είναι χωρίς περιβάλλον (γνωρίζουμε ήδη αυτό).

* L2 ={c m d m | m ≥ 0} είναι απαλλαγμένο από το περιβάλλον (παρόμοιο με το L1).

* L =L1L2 (η συγκόλληση των L1 και L2).

* Δεδομένου ότι τα L1 και L2 είναι απαλλαγμένα από το περιβάλλον και οι γλώσσες χωρίς περιβάλλοντα κλείνουν υπό συνδυασμό, το L είναι χωρίς περιβάλλοντα.

4. Η άντληση λεμμάτων για γλώσσες χωρίς περιβάλλοντα (για την απόδειξη μιας γλώσσας είναι * όχι * χωρίς περιβάλλον):

* ΣΗΜΑΝΤΙΚΟ: Το λεμόνι άντλησης χρησιμοποιείται για να διαψεύσει * ότι μια γλώσσα είναι απαλλαγμένη από το περιβάλλον. Δεν μπορεί να χρησιμοποιηθεί για να αποδείξει ότι μια γλώσσα * είναι * χωρίς περιβάλλον.

* Πώς λειτουργεί: Το λεμόνι αντλίας δηλώνει ότι για οποιαδήποτε γλώσσα χωρίς περιβάλλοντα L, υπάρχει ένα μήκος άντλησης «p» έτσι ώστε κάθε συμβολοσειρά σε L με μήκος τουλάχιστον «p» να μπορεί να χωριστεί σε πέντε μέρη, s =uvxyz, πού:

1. | VXY | ≤ P (το μεσαίο τμήμα δεν είναι πολύ μεγάλο)

2. | Vy | ≥ 1 (το μέρος που πρέπει να επαναληφθεί δεν είναι άδειο)

3. Για όλα ≥ 0, uv i xy i Το Z είναι στο L (μπορείτε να επαναλάβετε το 'V' και το 'Y' κάθε φορά και η συμβολοσειρά που προκύπτει εξακολουθεί να βρίσκεται στη γλώσσα).

* Απόδειξη με αντίφαση:

1. Υποθέστε ότι η γλώσσα είναι απαλλαγμένη από το περιβάλλον.

2. Υποθέστε ότι υπάρχει ένα μήκος άντλησης «Ρ» όπως περιγράφεται στο Λέμα.

3. Επιλέξτε μια συμβολοσειρά στη γλώσσα που είναι μεγαλύτερη από το 'p'. Η επιλογή του 's' είναι κρίσιμη. Θα πρέπει να έχει ιδιότητες που καθιστούν προβληματική την άντληση.

4. Εξετάστε * όλους τους πιθανούς * τρόπους για να διαιρέσετε το 'S' σε 'uvxyz' που ικανοποιούν τις συνθήκες 1 και 2 του λεμόνι άντλησης.

5. Για το κάθε * πιθανό τμήμα, δείξτε ότι υπάρχει ένα «i» (συνήθως i =0 ή i =2) έτσι ώστε uv i xy i z δεν είναι * στη γλώσσα.

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

Ποια μέθοδος χρήσης:

* Κατασκευή γραμματικής/PDA: Ο πιο συνηθισμένος και συχνά ευκολότερος τρόπος για να δείξετε μια γλώσσα * είναι * χωρίς περιβάλλον. Επιλέξτε όποιον (CFG ή PDA) είναι ευκολότερο να κατασκευαστεί για τη συγκεκριμένη γλώσσα. Εάν η γλώσσα φαίνεται να περιλαμβάνει ένθετες ή αναδρομικές δομές, μια γραμματική είναι συχνά ένα καλό σημείο εκκίνησης. Εάν η γλώσσα προσφέρεται σε μια συμπεριφορά που μοιάζει με στοίβα, σκεφτείτε να χρησιμοποιήσετε ένα PDA.

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

* άντληση λεμμά: Αποκλειστικά για την εμφάνιση μιας γλώσσας δεν είναι * χωρίς περιβάλλον.

Σημαντικές εκτιμήσεις:

* Οι κανονικές γλώσσες είναι χωρίς περιβάλλοντα: Κάθε κανονική γλώσσα είναι επίσης χωρίς περιβάλλον. Εάν μπορείτε να εμφανίσετε μια γλώσσα είναι τακτική (παρέχοντας DFA, NFA ή κανονική έκφραση), έχετε επίσης δείξει ότι είναι χωρίς περιβάλλον. Ωστόσο, συχνά ένα CFG ή PDA θα είναι η πιο απλή προσέγγιση εάν η γλώσσα είναι * προφανώς * χωρίς περιβάλλον.

* Μη deterministic PDAS: Σε γενικές γραμμές, οι PDA είναι μη αποικινιστικοί. Οι ντετερμινιστικές PDAs (DPDAs) είναι λιγότερο ισχυροί. Αποδέχονται ένα σωστό υποσύνολο των γλωσσών χωρίς περιβάλλοντα (που ονομάζεται ντετερμινιστικές γλώσσες χωρίς περιβάλλον). Εκτός αν δηλώνεται ρητά, μπορείτε να υποθέσετε ότι έχετε να αντιμετωπίσετε με γενικές (μη καθοριστικές) γλώσσες χωρίς περιβάλλοντα.

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

* Παραδείγματα: Εργαστείτε μέσω πολυάριθμων παραδειγμάτων για να αποκτήσετε καλή κατανόηση αυτών των τεχνικών. Η πρακτική είναι το κλειδί!

Συνοπτικά, για να αποδειχθεί * μια γλώσσα είναι απαλλαγμένη από το περιβάλλον, δημιουργήστε ένα CFG ή PDA για αυτό, ή να επιδείξει την ευνοϊκή της περιεκτικότητα σε ιδιότητες κλεισίματος. Χρησιμοποιήστε το λεμόνι άντλησης για γλώσσες χωρίς περιβάλλοντα για να δείξετε ότι μια γλώσσα δεν είναι * χωρίς περιβάλλον. Καλή τύχη!