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

Το λεμόνι άντλησης για γλώσσες χωρίς περιβάλλοντα (CFLS) είναι ένα ισχυρό εργαλείο για να αποδείξει ότι μια δεδομένη γλώσσα δεν είναι * χωρίς περιβάλλον. Είναι μια απόδειξη από την τεχνική αντίφασης. Εδώ είναι η γενική διαδικασία και οι βασικές ιδέες:

1. Δηλώστε το λεμμά (προσεκτικά!)

Πριν ξεκινήσετε, είναι απαραίτητο να κατανοήσετε τη δήλωση της αντλίας Lemma *ακριβώς *. Εδώ είναι μια κοινή διατύπωση:

άντληση λεμμά για CFLS:

Εάν το L είναι μια γλώσσα χωρίς περιβάλλον, τότε υπάρχει ένας ακέραιος *p *(το "μήκος άντλησης") έτσι ώστε για κάθε συμβολοσειρά *s *σε l με μήκος μεγαλύτερο ή ίσο με *p *(| s | ≥ *p *), *s *μπορεί να χωριστεί σε πέντε υποστρώματα:

* | VXY | ≤ * p * (το μεσαίο τμήμα που αντλείται δεν είναι πολύ μεγάλο)

* | Vy | ≥ 1 (το αντλημένο τμήμα δεν είναι άδειο)

* Για όλους * i * ≥ 0, * uv i xy i Το Z* είναι επίσης στο L (αντλώντας 'V' και 'y' οποιεσδήποτε φορές διατηρεί τη συμβολοσειρά στη γλώσσα)

2. Υποθέστε ότι η γλώσσα * είναι * χωρίς περιβάλλον

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

3. Ας * p * να είναι το μήκος άντλησης

Δεδομένου ότι έχετε υποθέσει ότι το * L * είναι χωρίς περιβάλλον, το λεμόνι αντλίας * πρέπει να ισχύει. Αυτό σημαίνει ότι υπάρχει μήκος άντλησης * p * (το οποίο δεν γνωρίζετε την ακριβή τιμή του). Είναι σημαντικό να θυμάστε ότι ο αντίπαλος (ποιος γνωρίζει ότι η γλώσσα δεν είναι *χωρίς περιβάλλον και προσπαθεί να σας ξεγελάσει) παίρνει να επιλέξει *p *. Ο στόχος σας είναι να βρείτε μια συμβολοσειρά που * ανεξάρτητα από την αξία του P * επιλέγεται, οι συνθήκες του λεμφικού λεμφικού οδηγούν σε μια αντίφαση.

4. Επιλέξτε μια συμβολοσειρά*s*∈*l*έτσι ώστε |*s*| ≥ *p *

Αυτό είναι ένα κρίσιμο βήμα. Πρέπει να επιλέξετε προσεκτικά μια συμβολοσειρά *s *που ανήκει στη γλώσσα *l *και έχει μήκος μεγαλύτερο από ή ίσο με *p *. Η επιλογή του * S * είναι ζωτικής σημασίας για την εργασία απόδειξης. Σκεφτείτε τη δομή των χορδών στη γλώσσα σας και πώς η άντληση μπορεί να επηρεάσει αυτή τη δομή. Ο στόχος είναι να διαλέξετε μια συμβολοσειρά των οποίων οι ιδιότητες θα παραβιαστούν όταν αντλούνται «V» και «Y» με τρόπο που υπαγορεύεται από το λεμμάτ. Αυτή η επιλογή *συχνά *περιλαμβάνει τον καθορισμό ορισμένων τμημάτων της συμβολοσειράς με βάση την τιμή *p *.

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

5. Εξετάστε όλες τις πιθανές αποσυνθέσεις * S =UVXYZ * Ικανοποιητική | VXY | ≤ * p * και | vy | ≥ 1

Το λεμόνι αντλίας δηλώνει ότι*κάθε συμβολοσειρά*s*με |*s*| ≥ * P * μπορεί να χωριστεί με αυτόν τον τρόπο. Έτσι, * ο αντίπαλός σας * παίρνει για να επιλέξει πώς * s * χωρίζεται σε * uvxyz * (υπόκειται στους περιορισμούς | vxy | ≤ * p * και | vy | ≥ 1). Ωστόσο, μπορείτε να εξετάσετε όλα τα δυνατά τέτοια τμήματα. Πρέπει να δείξετε ότι *ανεξάρτητα από το πώς *ο αντίπαλος επιλέγει *u *, *v *, *x *, *y *, και *z *, μπορείτε να αντλήσετε τη συμβολοσειρά για να πάρετε μια αντίφαση.

Συχνά, αυτό περιλαμβάνει την εξέταση διαφορετικών *περιπτώσεων *με βάση το πού *V *και *y *θα μπορούσε ενδεχομένως να εμπίπτει στη συμβολοσειρά *s *. Για κάθε περίπτωση, θα αναλύσετε τι συμβαίνει όταν αντλείτε *V *και *y *.

6. Δείξτε ότι για μερικά *i *≥ 0, η συμβολοσειρά *uv i xy i z * δεν είναι * σε * l *

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

* Πώς να δείξετε * uv i xy i z * δεν είναι σε * l *:Αυτό θα εξαρτηθεί από τη συγκεκριμένη γλώσσα. Θα χρειαστεί να αποδείξετε ότι η αντλημένη συμβολοσειρά παραβιάζει τις καθοριστικές ιδιότητες του *l *. Οι κοινές στρατηγικές περιλαμβάνουν:

* δείχνοντας ότι η συμβολοσειρά έχει τώρα άνισους αριθμούς συμβόλων που ήταν προηγουμένως ίσα. Για παράδειγμα, εάν το * L * απαιτεί τον ίδιο αριθμό «Α και« Β, δείχνετε ότι η άντληση προκαλεί την αμέτρηση του μέτρου.

* δείχνοντας ότι η σειρά των συμβόλων είναι τώρα λανθασμένη. Για παράδειγμα, αν * L * απαιτεί όλα τα «Α» να έρθουν μπροστά σε όλα τα «B, δείχνετε ότι η άντληση μπορεί να βάλει ένα« Β »πριν από το« Α ».

* δείχνοντας ότι μια μαθηματική σχέση μεταξύ των μετρήσεων δεν κατέχει πλέον. Για παράδειγμα, εάν το * L * απαιτεί τον αριθμό των «Α, να είναι διπλάσιο από τον αριθμό των« Β, δείχνετε ότι η άντληση παραβιάζει αυτή τη σχέση.

7. Καταλήγουν στο συμπέρασμα ότι το * l * δεν είναι * χωρίς περιβάλλον

Δεδομένου ότι έχετε δείξει ότι η υπόθεση ότι το * L * είναι απαλλαγμένο από το περιβάλλον οδηγεί σε μια αντίφαση (το λεμόνι αντλίας πρέπει να κρατήσει, αλλά έχετε δείξει μια περίπτωση όπου δεν το κάνει), μπορείτε να καταλήξετε στο συμπέρασμα ότι η αρχική σας παραδοχή ήταν ψευδής. Επομένως, το * l * δεν είναι γλώσσα χωρίς περιβάλλοντα.

Παράδειγμα:Η γλώσσα l ={a n B n c n | n ≥ 0}

Ας αποδείξουμε ότι * l * ={a n B n c n | n ≥ 0} δεν είναι απαλλαγμένο από το περιβάλλον χρησιμοποιώντας το λεμλά της άντλησης.

1.

2. ας * p * είναι το μήκος άντλησης Εγγυημένη από το λεμόνι άντλησης.

3. Επιλέξτε μια συμβολοσειρά *s *: Έστω*s*=a *p* B *p* c *p* . Σαφώς,*s*∈*l*και |*s*| =3*p*≥*p*.

4. ≤ * p * και | vy | ≥ 1: Πρέπει να εξετάσουμε πού μπορούν να εντοπιστούν τα υποστρώματα *v *και *y *μέσα *s *. Ο κρίσιμος περιορισμός είναι ότι | VXY | ≤ *p *. Αυτό περιορίζει σημαντικά τις δυνατότητες:

* Περίπτωση 1:* Vxy * αποτελείται μόνο από το 'a's. Τότε * v * =a j και * y * =a k Για μερικά*j*,*k*≥ 0 και*j + k*≥ 1. B *p* c *p* . Δεδομένου ότι * j + k * ≥ 1, αυτή η συμβολοσειρά έχει λιγότερα από * p * 'a's, αλλά εξακολουθεί να έχει * p *' b και * p * 'c's. Επομένως, δεν είναι στο *l *.

* Περίπτωση 2:* VXY * αποτελείται μόνο από το «B» Τότε * v * =b j και * y * =b k Για μερικά*j*,*k*≥ 0 και*j + k*≥ 1. B *p-j-k* c *p* . Και πάλι, ο αριθμός των «Β είναι μικρότερος από *p *, ενώ οι αριθμοί των« Α και «C παραμένουν *p *, οπότε δεν είναι στο *l *.

* Περίπτωση 3:* VXY * αποτελείται μόνο από 'c. Τότε * v * =c j και * y * =c k Για μερικά*j*,*k*≥ 0 και*j + k*≥ 1. B *p* c *p-j-k* . Ο αριθμός των 'C είναι μικρότερος από *p *, ενώ οι αριθμοί των' a και 'b παραμένουν *p *, έτσι δεν είναι στο *l *.

* Περίπτωση 4:* Vxy * αποτελείται από 'a's και' b. Από το | VXY | ≤ *p *, δεν μπορεί να συμπεριλάβει κανένα 'c's επειδή όλα τα *p *' a's και *p *'b πρέπει να προηγούνται οποιουδήποτε' c. Από το | Vy | ≥ 1, τουλάχιστον ένα από τα * V * ή * y * πρέπει να περιέχει έναν χαρακτήρα. Επομένως * v * =a j B k και * y * =a l B m Για μερικούς *j *, *k *, *l *, *m *≥ 0 και *j + k + l + m *≥ 1, με τουλάχιστον ένα από το «Α» ή «Β» σε *V *ή *y *.

Εάν αντλήσουμε (*i*=2), παίρνουμε τη συμβολοσειρά A *p+j+l* B *p+k+m* c *p* . Εάν το * k + m * είναι μηδέν (έτσι * v * και * y * περιέχει μόνο 'a's) ο αριθμός των' a αυξάνεται, αλλά ο αριθμός των 'b παραμένει ο ίδιος. Το αποτέλεσμα είναι ένα *p+j+l* B *p* c *p* που δεν είναι πλέον στη γλώσσα. Εάν το * j + l * είναι μηδέν (έτσι * v * και * y * περιέχει μόνο 'b), ο αριθμός των' B αυξάνεται, αλλά ο αριθμός των 'Α παραμένει ο ίδιος. Το αποτέλεσμα είναι ένα *p* B *p+k+m* c *p* που δεν είναι πλέον στη γλώσσα. Εάν και τα δύο *k+m *και *j+l *είναι μεγαλύτερα από το μηδέν, τότε *uv 2 xy 2 Το z* έχει περισσότερα 'a και' b από 'c, που σημαίνει ότι δεν μπορεί να είναι της φόρμας a n B n c n .

* Περίπτωση 5:* Vxy * αποτελείται από 'b και' c. Αυτό είναι συμμετρικό στην περίπτωση 4. Και πάλι, η άντληση θα έχει ως αποτέλεσμα μια συμβολοσειρά που δεν βρίσκεται στη γλώσσα.

5. αντίφαση: Σε κάθε πιθανή περίπτωση, έχουμε δείξει ότι υπάρχει ένα *i *έτσι ώστε *uv i xy i z*δεν είναι στο*l*. Αυτό έρχεται σε αντίθεση με το λεμμάνικο άντλησης.

6. Συμπέρασμα: Επομένως, η αρχική μας υπόθεση ότι το * L * είναι χωρίς περιβάλλον πρέπει να είναι ψευδής. Έτσι, * l * ={a n B n c n | n ≥ 0} δεν είναι χωρίς περιβάλλον.

Συμβουλές για τη χρήση του λεμφικού άντλησης:

* Κατανοήστε ακριβώς το λεμμά: Γνωρίστε την ακριβή δήλωση και προϋποθέσεις.

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

* Ανάλυση προσεκτικών περιπτώσεων: Εξετάστε όλες τις πιθανές θέσεις για *V *και *y *μέσα *S *, δεδομένου των περιορισμών | VXY | ≤ * p * και | vy | ≥ 1.

* Επιλέξτε το σωστό * i *:Πειραματιστείτε με *i *=0, *i *=2 ή άλλες τιμές για να βρείτε αυτό που αποδεικνύει σαφώς την παραβίαση του *l *. Μερικές φορές * i * =0 θα προκαλέσει κάτι να εξαφανιστεί, και * i * =2 θα προκαλέσει κάτι να αντιγραφεί.

* Να είστε σαφείς και αυστηροί: Εξηγήστε ακριβώς γιατί η αντλημένη συμβολοσειρά δεν είναι πλέον σε *l *. Ανατρέξτε στις καθοριστικές ιδιότητες της γλώσσας.

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