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

Υπάρχουν διάφοροι τρόποι για να αποδειχθεί ότι μια γλώσσα δεν είναι απαλλαγμένη από το περιβάλλον. Οι πιο συνηθισμένες μεθόδους βασίζονται στην απόδειξη της γλώσσας παραβιάζουν τις ιδιότητες που ενυπάρχουν στις γλώσσες χωρίς περιβάλλοντα (CFLs):

1. Άντληση λεμμά για γλώσσες χωρίς περιβάλλοντα: Αυτή είναι η πιο ευρέως χρησιμοποιούμενη τεχνική. Το λεμόνι αντλίας δηλώνει ότι για κάθε CFL L, υπάρχει μια σταθερή * p * (το μήκος άντλησης) έτσι ώστε κάθε συμβολοσειρά * w * σε l με μήκος | w | ≥ *p *μπορεί να γραφτεί ως *uvxyz *, πού:

* | VXY | ≤ *p *

* | Vy | ≥ 1

* * uv i xy i z* ∈ L για όλα* i* ≥ 0

Για να αποδείξετε ότι μια γλώσσα δεν είναι * χωρίς περιεχόμενο χρησιμοποιώντας το λεμλά της άντλησης:

1. Ας υποθέσουμε ότι, για χάρη της αντίφασης, ότι η γλώσσα * l * είναι χωρίς περιβάλλον.

2. Επιλέξτε μια συμβολοσειρά: Επιλέξτε μια συμβολοσειρά *W *σε *L *με μήκος τουλάχιστον το μήκος άντλησης *P *(θα χρειαστεί συχνά να επιλέξετε στρατηγικά *W *).

3. αντλούν τη συμβολοσειρά: Προσπαθήστε να αποσυντεθείτε * w * σε * uvxyz * ικανοποιώντας τις συνθήκες του λεμμά.

4. Βρείτε μια αντίφαση: Δείξτε ότι για μερικούς *i *, *uv i xy i z*δεν είναι*στο*l*. Αυτό έρχεται σε αντίθεση με το λεμμά που αντλείται, αποδεικνύοντας ότι η αρχική παραδοχή (ότι το * L * είναι χωρίς περιβάλλον) πρέπει να είναι ψευδής.

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

1. Το L είναι χωρίς περιεχόμενο.

2. Επιλέξτε μια συμβολοσειρά: Ας * w * =a p B p c p (όπου * p * είναι το μήκος άντλησης).

3. αντλούν τη συμβολοσειρά: Ανεξάρτητα από το πώς αποσυντίθεις *w *σε *uvxyz *, η άντληση θα παραβιάσει αναπόφευκτα το a n B n c n δομή. Για παράδειγμα, εάν το * VXY * περιέχει μόνο 'Α, η άντληση θα αυξήσει τον αριθμό των' Α χωρίς να αυξήσει τον αριθμό των 'B και' C. Παρόμοια ζητήματα προκύπτουν εάν το * VXY * περιέχει μόνο 'B ή' C ή ένα μείγμα που δεν διατηρεί την ισότιμη αναλογία.

4. αντίφαση: Επομένως, υπάρχει ένα *i *έτσι ώστε *uv i xy i z* ∉ l, Αντίθετα το λεμμά αντλίας. Έτσι, το L δεν είναι χωρίς περιβάλλον.

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

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

4. Θεώρημα του Parikh: Αυτό το θεώρημα σχετίζεται με τον αριθμό των περιστατικών κάθε συμβόλου σε χορδές μιας γλώσσας. Παρόλο που δεν χρησιμοποιείται άμεσα για να αποδείξει μια γλώσσα * δεν είναι * χωρίς περιβάλλον, μπορεί μερικές φορές να βοηθήσει να δείξει ότι η δομή μιας γλώσσας είναι ασυμβίβαστη με τους περιορισμούς που επιβάλλονται από την CFLS. Συχνά χρησιμοποιείται σε συνδυασμό με άλλες τεχνικές.

Εν ολίγοις, το λεμόνι άντλησης είναι η πιο συνηθισμένη και γενικά αποτελεσματική μέθοδος για την απόδειξη μιας γλώσσας δεν είναι απαλλαγμένη από το περιβάλλον. Ωστόσο, η επιλογή της μεθόδου εξαρτάται από τη δομή της συγκεκριμένης γλώσσας και την ευκολία με την οποία μπορεί να εφαρμοστεί κάθε τεχνική. Το Lemma του Ogden προσφέρει περισσότερη ισχύ όταν χρειάζεται και οι ιδιότητες κλεισίματος μπορούν να παρέχουν συμπληρωματικά στοιχεία.