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

Το λεμόνι άντλησης για κανονικές γλώσσες είναι ένα ισχυρό εργαλείο για να αποδείξει ότι μια γλώσσα δεν είναι * κανονική. Λειτουργεί με αντίφαση:Υποθέτετε ότι η γλώσσα * είναι * τακτική και στη συνέχεια δείχνει ότι αυτή η υπόθεση οδηγεί σε μια αντίφαση του ίδιου του λεμμά. Δείτε πώς λειτουργεί:

1. Η δήλωση αντλίας Lemma:

Το λεμόνι αντλίας δηλώνει ότι για οποιαδήποτε κανονική γλώσσα L, υπάρχει ένα μήκος άντλησης P έτσι ώστε κάθε συμβολοσειρά W σε L με μήκος | W | ≥ p μπορεί να χωριστεί σε τρία υποσχέσεις, w =xyz, ικανοποιώντας τις ακόλουθες προϋποθέσεις:

* | xy | ≤ p: Το μήκος της συγκόλλησης των x και y είναι μικρότερο ή ίσο με το p.

* | y |> 0: Το υποσύνολο y δεν είναι άδειο.

* για όλα i ≥ 0, xy i z ∈ L: Η άντληση y μηδέν ή περισσότερες φορές (συμπεριλαμβανομένης της αφαίρεσης του εξ ολοκλήρου όταν i =0) έχει ως αποτέλεσμα μια συμβολοσειρά που εξακολουθεί να βρίσκεται στη γλώσσα L.

2. Στρατηγική απόδειξης:

Για να αποδείξετε ότι μια γλώσσα L δεν είναι τακτική χρησιμοποιώντας το λεμμά αντλίας, ακολουθήστε αυτά τα βήματα:

* υποθέστε ότι το L είναι κανονικό: Ξεκινήστε υποθέτοντας, για χάρη της αντίφασης, ότι το L είναι μια κανονική γλώσσα.

* Επιλέξτε ένα μήκος άντλησης P: Το λεμόνι άντλησης εγγυάται την ύπαρξη μήκους αντλίας P. Δεν χρειάζεται να βρείτε την πραγματική του αξία, απλώς ανατρέξτε σε αυτό ως «p».

* Επιλέξτε μια συμβολοσειρά w ∈ L έτσι ώστε | w | ≥ p: Επιλέξτε προσεκτικά μια συμβολοσειρά W από τη γλώσσα L του οποίου το μήκος είναι τουλάχιστον p. Η επιλογή του W είναι κρίσιμη. Πρέπει να σας επιτρέψει να δημιουργήσετε μια αντίφαση στο επόμενο βήμα. Αυτό συχνά περιλαμβάνει χορδές με μια συγκεκριμένη δομή που σχετίζεται με τον ορισμό της γλώσσας.

* Δείξτε ότι καμία αποσύνθεση W =XYZ ικανοποιεί τις συνθήκες άντλησης λεμμάτων: Αυτή είναι η καρδιά της απόδειξης. Για * οποιαδήποτε πιθανή αποσύνθεση του W σε XYZ ικανοποιώντας | XY | ≤ p και | y |> 0, πρέπει να δείξετε ότι υπάρχουν κάποια ≥ 0 έτσι ώστε xy i z ∉ L. Αυτό σημαίνει ότι η άντληση y παραβιάζει τον ορισμό της γλώσσας L. Συχνά, αποδεικνύετε αυτό δείχνοντας ότι η άντληση y θα:είτε:

* Εισάγετε μια ανισορροπία: Αλλάξτε τον αριθμό των περιστατικών κάποιου συμβόλου, παραβιάζοντας έναν περιορισμό καταμέτρησης στο L.

* Δημιουργήστε μια μη έγκυρη δομή: Σπάστε το μοτίβο ή τη δομή που απαιτείται από τον ορισμό του L.

* Εισάγετε ένα μη έγκυρο υποσύνολο: Δημιουργήστε ένα υποσύνολο που δεν ανήκει στη γλώσσα.

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

Παράδειγμα:Αποδείξη {a n B n | n ≥ 0} δεν είναι τακτική:

Έστω l ={a n B n | n ≥ 0}.

1.

2. Επιλέξτε P: Αφήστε το P να είναι το μήκος άντλησης.

3. Επιλέξτε W: Ας w =a p B p . Σαφώς, w ∈ L και | w | ≥ p.

4. Ας εξετάσουμε οποιαδήποτε αποσύνθεση w =xyz έτσι ώστε | xy | ≤ p και | y |> 0. Δεδομένου ότι | xy | ≤ p, y πρέπει να αποτελείται * μόνο * του Α (επειδή το y είναι ένα υποσύνολο από τους πρώτους χαρακτήρες p). Έτσι, y =a k Για μερικά k> 0. Τώρα, αντλούν y μηδενικές φορές:xy 0 z =a p-k B p . Αυτή η συμβολοσειρά δεν είναι στο L επειδή ο αριθμός των Α και Β είναι διαφορετικός. Αυτό έρχεται σε αντίθεση με το λεμμάνικο άντλησης.

5. Δεδομένου ότι έχουμε φτάσει σε μια αντίφαση, η παραδοχή μας ότι το L είναι κανονικό πρέπει να είναι ψευδές. Επομένως, l ={a n B n | n ≥ 0} δεν είναι κανονική γλώσσα.

Το κλειδί είναι να επιλέξετε προσεκτικά τη συμβολοσειρά `w` και να αναλύσετε έξυπνα όλες τις πιθανές αποσύνσεις` xyz` για να δείξετε ότι η άντληση `y` οδηγεί πάντα σε μια συμβολοσειρά έξω από τη γλώσσα. Όσο πιο περίπλοκη είναι η γλώσσα, τόσο πιο περίπλοκη είναι η επιλογή του «w» και η ανάλυση γίνεται.