9.7 Το Λήμμα Άντλησης για context free γλώσσες, και η εφαρμογή του

Όπως και στην περίπτωση των κανονικών γλωσσών υπάρχει και για τις context free γλώσσες, ένα «<Λήμμα Άντλησης» που είναι πολύ χρήσιμο στο να αποδεικνύουμε ότι ορισμένες γλώσσες δεν είναι context free. Η μορφή του είναι πολύ παρόμοια με το Λήμμα Άντλησης για κανονικές γλώσσες κα ο τρόπος χρήσης του επίσης.

Θεώρημα 9.3   (Λήμμα Άντλησης για context free γλώσσες) Έστω ότι η γλώσσα $L$ είναι context free. Τότε υπάρχει ένας φυσικός αριθμός $n$ τέτοιος ώστε για κάθε λέξη $z \in L$ με ${\left\vert{z}\right\vert} \ge n$ να μπορούμε να γράψουμε

$$z = uvwxy,$$

όπου

(α)

${\left\vert{vx}\right\vert} \ge 1$,

(β)

${\left\vert{vwx}\right\vert} \le n$, και

(γ)

για κάθε $i\ge 0$ ισχύει $uv^iwx^iy \in L$.

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

Παράδειγμα 9.1   Η γλώσσα $L_1 = {\left\{{a^nb^nc^n:  n\ge 0}\right\}}$ δεν είναι context free

Ας υποθέσουμε ότι η $L_1$ είναι context free. Έστω τότε $n$ ο αριθμός που αναφέρεται στο Θεώρημα 9.3 και $z = a^{2n}b^{2n}c^{2n} \in L_1$. Από το Θεώρημα 9.3 η λέξη $z$ γράφεται ως $z = uvwxy$ όπου ισχύουν τα συμπεράσματα του Θεωρήματος. Παρατηρούμε ότι η λέξη $vwx$, που σύμφωνα με το Θεώρημα έχει μήκος το πολύ $n$, δε μπορεί να περιέχει και $a$ και $c$, ακριβώς επειδή το μήκος της δε φτάνει να «γεφυρώσει» τα $b$ της λέξης $z$. Χωρίς βλάβη της γενικότητας υποθέτουμε ότι από τη λέξη αυτή λείπουν τα $a$ (και το επιχείρημα είναι εντελώς παρόμοιο αν λείπουν τα $c$). Από το Θεώρημα 9.3 έπεται ότι η λέξη $uwy \in L_1$ (εφαρμόσαμε το Θεώρημα με $i=0$). Αλλά για να πάμε από τη λέξη $z$ στην $uwy$ σβήσαμε το $u$ και το $x$, τα οποία δεν έχουν $a$ μέσα, άρα το πλήθος των $a$ στη λέξη $uwy$ έχει παραμείνει $2n$. Το μήκος της $uwy$ όμως είναι αυστηρά μικρότερο του $6n$ (εδώ χρησιμοποιούμε το (α) από τα συμπεράσματα του Θεωρήματος), άρα δε μπορεί η λέξη $uwy$ να ανήκει στην $L_1$, όπως είχαμε υποθέσει. Άρα η $L_1$ δεν είναι context free.

Άσκηση 9.6   Δείξτε ότι η γλώσσα ${\left\{{xx:  x\in{\left\{{0,1}\right\}}^*}\right\}}$ δεν είναι context free.

Άσκηση 9.7   Δείξτε ότι η γλώσσα ${\left\{{(ab)^k(cd)^k:   k\in{\mathbb{N}}}\right\}}$ δεν είναι κανονική.