7.10 Το Λήμμα Άντλησης και μη κανονικές γλώσσες

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

Πόσες όμως διαφορετικές πεπερασμένες περιγραφές υπάρχουν;

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

Το γιατί το σύνολο όλων των πεπερασμένων εκφράσεων (πάνω από ένα σταθερό αλφάβητο $\Sigma$) είναι αριθμήσιμο είναι απλό. Αφού το $\Sigma$ είναι πεπερασμένο υπάρχουν πεπερασμένες σε πλήθος εκφράσεις που μπορούν να φτιάξουμε με μήκος $n$, για κάθε $n$. Για την ακρίβεια, υπάρχουν το πολύ ${\left\vert{\Sigma}\right\vert}^n$ τέτοιες εκφράσεις. Για να απαριθμήσουμε λοιπόν το σύνολο όλων των πεπερασμένων εκφράσεων, αριθμούμε πρώτα τις εκφράσεις μήκους 1, μετά αυτές μήκους 2, και συνεχίζουμε κατ' αυτόν τον τρόπο, ώστε δε μένει τίποτα αμέτρητο.

Είναι αρκετά πιο δύσκολο (και παραλείπουμε την απόδειξη) να δούμε ότι το σύνολο όλων των υποσυνόλων οποιουδήποτε άπειρου συνόλου δεν είναι αριθμήσιμο. Έτσι, το σύνολο όλων των γλωσσών πάνω από το $\Sigma$, δηλ. το σύνολο όλων των υποσυνόλων του άπειρου συνόλου $\Sigma^*$ δεν είναι αριθμήσιμο. Άρα υπάρχει κάποια γλώσσα που δεν έχει αντίστοιχη πεπερασμένη περιγραφή, οπότε δεν είναι κανονική.

Το παραπάνω είναι ένα πολύ γενικό επιχείρημα, όπως είπαμε, και δεν εξαρτάται σχεδόν καθόλου από το τι εννοούμε κανονική γλώσσα, παρά μόνο ότι, ό,τι κι αν εννοούμε, η κανονική γλώσσα μπορεί να περιγραφεί πλήρως με μια πεπερασμένη ακολουθία από γράμματα, διαλεγμένα από ένα πεπερασμένο αλφάβητο. Με τον ίδιο τρόπο φαίνεται, π.χ. ότι υπάρχουν συναρτήσεις $f:{\mathbb{N}}\to{\mathbb{N}}$ που δεν είναι υπολογίσιμες από πρόγραμμα, ουσιαστικά ότι κι αν εννούμε με αυτό. Ας πούμε για παράδειγμα ότι θεωρούμε μια τέτοια συνάρτηση υπολογίσιμη αν υπάρχει ένα πρόγραμμα σε κάποια γλώσσα προγραμματισμού, ας πούμε την python που υπολογίζει τη συνάρτηση αυτή. Μα ένα πρόγραμμα αποτελεί πεπερασμένη περιγραφή της συνάρτησης, άρα, επειδή το πλήθος των συναρτήσεων $f:{\mathbb{N}}\to{\mathbb{N}}$ δεν είναι αριθμήσιμο, υπάρχει κάποια στην οποία δεν αντιστοιχεί πρόγραμμα, που δεν είναι δηλ. υπολογίσιμη.

Δε βοηθάει όμως αυτό το επιχείρημα στο να αποδείξει κανείς ότι συγκεκριμένες γλώσσες δεν είναι κανονικές. Αν και γνωρίζουμε δηλ. ότι οι περισσότερες γλώσσες (υπό την έννοια του πληθαρίθμου) δεν είναι κανονικές, είναι παρ' όλα αυτά δύσκολο να δείξουμε αυτό για μια συγκεκριμένη γλώσσα που μας δίδεται, π.χ. για την

$$L_1 = {\left\{{0^n1^n:   n=0,1,2,\ldots}\right\}}.$$

Αυτή η γλώσσα απαρτίζεται από όλες τις λέξεις που έχουν αρχικά μια ομάδα από μηδενικά και μετά μια ίση σε μήκος ομάδα από άσους, και τίποτε άλλο. Θα δούμε σε λίγο ένα τρόπο απόδειξης του ότι η $L_1$ δεν είναι κανονική. Διαισθητικά όμως ο λόγος είναι ο εξής (το παρακάτω δεν αποτελεί απόδειξη): ένα αυτόματο είναι ουσιαστικά ισοδύναμο με ένα υπολογιστή σαν κι αυτούς που ξέρουμε με μόνο τον περιορισμό ότι ο υπολογιστής αυτός έχει πεπερασμένη και σταθερή μνήμη, δεν εξαρτάται δηλ. η ποσότητα της μνήμης του από το πρόβλημα που έχει να λύσει. Αν είχαμε ένα πρόγραμμα που τρέχει σε ένα τέτοιο υπολογιστή και το οποίο αναγνωρίζει τη γλώσσα $L_1$, αυτό το πρόγραμμα θα είχε πρόσβαση σε μνήμη της οποίας το μήκος δε μπορεί να εξαρτάται από το μήκος της λέξης προς αναγνώριση. Όμως, δε μπορούμε να φανταστούμε ένα πρόγραμμα (αλγόριθμο) που θα αποφασίζει αν μια λέξη ανήκει στην $L_1$ ή οχι χωρίς να «θυμάται» κάπου το πόσα μηδενικά έχει δει. Κι αυτό δε γίνεται αν ο αριθμός των μηδενικών είνάι πολύ μεγάλος, γιατί όσο αυξάνει το πλήθος των μηδενικών τόσο αυξάνει, χωρίς άνω φράγμα, το πλήθος των ψηφίων (η μνήμη) που χρειαζόμαστε για να αποθηκεύσουμε τον αριθμό αυτό.

Είναι δύσκολο να μετατρέψουμε το παραπάνω διαισθητικό επιχείρημα σε απόδειξη, οπότε η μέθοδος που ακολουθούμε για να δείξουμε ότι η $L_1$ δεν είναι κανονική είναι αρκετά διαφορετική. Χρησιμοποιούμε το ακόλουθο πολύ χρήσιμο λήμμα.

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

$$z = uvw, (u,v,w \in \Sigma^*, {\left\vert{v}\right\vert}\ge 1, {\left\vert{uv}\right\vert} \le n),$$

ούτως ώστε για κάθε $i=0,1,2,\ldots$, η λέξη $uv^iw \in L$ (αυτή είναι η λέξη που αρχίζει με $u$ ακολουθείται από την $v$ οποιοδήποτε πεπερασμένο αριθμό από φορές - ακόμη και 0-και τελειώνει με $w$).

Μια εναλλακτική μετάφραση του Pumping Lemma θα μπορούσε να είναι «Λήμμα Φουσκώματος». Είτε με τη μια είτε με την άλλη μετάφραση το Λήμμα Άντλησης χρησιμοποιείται για να παράγουμε (αντλούμε) νέες λέξεις μιας κανονικής γλώσσας από άλλες.

Απόδειξη. Έστω $M$ ένα DFA με ελάχιστο αριθμό καταστάσεων που αναγνωρίζει τη γλώσσα $L$, και έστω $n$ το πλήθος των καταστάσεων του $M$. Αν η λέξη $z$ αναγνωρίζεται τότε ξεκινώντας από την αρχική κορυφή $q_0$ καταλήγουμε διαβάζοντας την $z$, με ${\left\vert{z}\right\vert} = m \ge n$, σε κάποια τελική κορυφή $q_1$ διανύοντας ένα μονοπάτι πάνω στο $M$:

$$q_0 = q_{i_1} \to q_{i_2} \to \cdots \to q_{i_{m+1}} = q_1$$

όπου το πλήθος των ακμών είναι $m$ (μια ακμή για κάθε γράμμα της $z$) και άρα το πλήθος των κορυφών είναι $m+1 > n$. Συμπεραίνουμε ότι υπάρχουν κάποιες κορυφές που εμφανίζονται τουλάχιστον δύο φορές στο μονοπάτι. Από αυτές τις κορυφές ονομάζουμε $q$ αυτή που πρωτοεμφανίζεται για δεύτερη φορά στο μονοπάτι και ονομάζουμε $v$ τη λέξη που μεσολαβεί μέχρι την επόμενη εμφάνιση της $q$, ενώ $u$ ονομάζομε το πρόθεμα της $z$ μέχρι την πρώτη εμφάνιση της $q$ και $w$ ονομάζομε το επίθεμα της $z$ μετά τη δεύτερη εμφάνιση της $q$ (βλ. Σχήμα 7.17).

Σχήμα 7.17: Το μονοπάτι που αντιστοιχεί στη λέξη $uvw$

Είναι φανερό ότι ${\left\vert{v}\right\vert}\ge 1$ και ότι ${\left\vert{uv}\right\vert}\le n$, αφού σίγουρα όταν θα έχουμε διαβάσει το $n$-οστό γράμμα της $z$ θα έχουμε ήδη δεί τουλάχιστον μια κορυφή δύο φορές, και ανάμεσα σε αυτές που έχουμε δεί δύο φορές η πρώτη είναι εξ ορισμού η $q$. Επίσης είναι φανερό ότι το βρόχο που ξεκινά και τελειώνει στην $q$ μπορούμε να μην το διανύσουμε καθόλου (οπότε δείχνουμε ότι η λέξη $uw \in L$) ή να τον διανύσουμε όσες φορές θέλουμε, ας πούμε $i$. Άρα η λέξη $uv^iw \in L$, όπως οφείλαμε να δείξουμε. $\qedsymbol$

Πώς χρησιμοποιούμε το Λήμμα Άντλησης για να δείξουμε ότι η γλώσσα $L_1$ δεν είναι κανονική; Υποθέτουμε ότι είναι και καταλήγουμε σε άτοπο. Αν είναι λοιπόν, υπάρχει, από το Λήμμα Άντλησης, ένας φυσικός αριθμός $n$, τέτοις ώστε αν $z\in L_1$ και ${\left\vert{z}\right\vert} \ge n$ τότε ισχύουν τα συμπεράσματα του Λήμματος. Έχουμε $z = 0^n1^n \in L_1$ και ${\left\vert{z}\right\vert} \ge n$, άρα $z = uvw$, με ${\left\vert{uv}\right\vert}\le n$ και μη κενό $v$, τέτοια ώστε για κάθε $i=0,1,\ldots$ έχουμε $uv^iw \in L_1$. Αυτό όμως δε γίνεται μια και η λέξη $uv^2w=uvvw$ έχει σίγουρα περισσότερα 0 απ' ότι 1, αφού, λόγω του ότι ${\left\vert{uv}\right\vert}\le n$, και το $u$ και το $v$ έχουν μόνο μηδενικά μέσα τους.

Ας δούμε τώρα άλλη μια εφαρμογή του λήμματος άντλησης σε παρόμοιο πρόβλημα. Για κάθε λέξη $x=\alpha_1\cdots\alpha_n$, $\alpha_i\in\Sigma$, ορίζουμε την αντεστραμμένη λέξη $x^R = \alpha_n \cdots \alpha_1$, να είναι η $x$ με αντεστραμμένη τη σειρά των γραμμάτων του. Ορίζουμε τη γλώσσα

$$L_2 = {\left\{{x\in (0+1)^*:    x = x^R}\right\}},$$

να απαρτίζεται από όλες εκείνες τις λέξεις που διαβάζονται το ίδιο από αριστερά και από τα δεξιά.

Δείχνουμε τώρα ότι η $L_2$ δεν είναι κανονική. Έστω ότι είναι και έστω $n$ ο φυσικός αριθμός του οποίου η ύπαρξη προκύπτει από το Λήμμα Άντλησης. Ορίζουμε τη λέξη $z = 1^n01^n$ που είναι στην $L_2$. Γράφεται τότε η $z$ ως $z = uvw$, με μη κενό $v$ και ${\left\vert{uv}\right\vert}\le n$, οπότε και οι λέξεις $u$.$v$ έχουν μέσα μόνο 1, ώστε $uv^iw \in L_2$, για $i=0,1,2,\ldots$. Αλλά προφανώς η λέξη $uw \notin L_2$ αφού αφαιρώντας το $v$ αφαιρέσαμε κάποιους άσους από την αριστερή ομάδα άων αλλά όχι από τη δεξιά ομάδα, οπότε έχουμε καταλήξει σε άτοπο, άρα η $L_2$ δεν είναι κανονική.

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

Άσκηση 7.35   Ποιες από τις παρακάτω γλώσσες του $(0+1)^*$ είναι κανονικές;

1. ${\left\{{0^{2n}:   n\ge 1}\right\}}$
2. ${\left\{{0^m1^n0^{m+n}:   m,n\ge 1}\right\}}$
3. Οι λέξεις που δεν έχουν τρία διαδοχικά μηδενικά
4. Λέξεις με τόσα μηδενικά όσα και άσους.
5. ${\left\{{xwx^R:    x,w \in (0+1)^+}\right\}}$