9.3 Ένα ενδιαφέρον παράδειγμα με πλήρη απόδειξη

Ας δούμε τώρα ένα παράδειγμα μιας CFG με παραπάνω από ένα μη τερματικό σύμβολο. Η γραμματική αυτή θα έχει ως γλώσσα της όλες τις λέξεις του ${\left\{{a,b}\right\}}^*$ που έχουν ίδιο πλήθος από $a$ και $b$. Θυμίζουμε εδώ ότι αυτή η γλώσσα δεν είναι κανονική (αποδεικνύεται εύκολα αυτό με χρήση του Λήμματος Άντλησης (Θεώρημα 7.6)).

Η γραμματική $G_1$ είναι η ακόλουθη:

1. $S \to a B \vert b A \vert \epsilon$
2. $A \to a S \vert b A A$
3. $B \to a B B \vert b S$

Θεώρημα 9.1   Η γλώσσα $L(G_1)$ απαρτίζεται από εκείνες τις λέξεις του ${\left\{{a,b}\right\}}^*$ με ίδιο πλήθος από $a$ και $b$.

Απόδειξη. Κατ' αρχήν τα μόνα τερματικά σύμβολα που εμφανίζονται στους κανόνες της $G_1$ είναι τα $a$ και $b$, άρα η $L(G_1)$ είναι υποσύνολο του ${\left\{{a,b}\right\}}^*$.

Ας συμβολίζουμε για μια λέξη $w$ του ${\left\{{a,b}\right\}}^*$ με $A(w)$ και $B(w)$ αντίστοιχα το πλήθος των $a$ και $b$ που περιέχει.

Πρέπει να δείξουμε ότι ισχύει $A(w) = B(w)$ αν και μόνο αν $S \underset{*}{\overset{G_1}{\Rightarrow}} w$. Αλλά αν προσπαθήσουμε να δείξουμε μόνο αυτό θα συναντήσουμε δυσκολίες. Παρ' ότι δείχνει αντιφατικό μας διευκολύνει το να δείξουμε παράλληλα και άλλες δύο προτάσεις. Έτσι θα δείξουμε με επαγωγή ως προς το μήκος της λέξης $w$ τις εξής τρείς ισοδυναμίες.

1. $w \in L(S)$ αν και μόνο αν $A(w) = B(w)$.
2. $w \in L(A)$ αν και μόνο αν $A(w) = B(w)+1$.
3. $w \in L(B)$ αν και μόνο αν $B(w) = A(w)+1$.

Ο ρόλος δηλ. των μη τερματικών συμβόλων $A$ και $B$ στην $G_1$ είναι να παράγουν όλες τις λέξεις με ακριβώς ένα $a$ παραπάνω (για το $A$) και ακριβώς ένα $b$ παραπάνω (για το $B$).

Όπως είπαμε συμβολίζουμε με $n$ το μήκος της λέξης $w$ και κάνουμε επαγωγή ως προς $n$. Αν $n=0$, τότε $w = \epsilon$ και $w$ παράγεται από το $S$ με τον τελευταίο κανόνα παραγωγής του $S$ ενώ δεν παράγεται από τα $A$ ή $B$, αφού όλοι οι κανόνες παραγωγής των $A$ και $B$ παράγουν μη κενές λέξεις. Βλέπουμε έτσι ότι ισχύουν και οι τρεις ισοδυναμίες για τη λέξη $w = \epsilon$, τη μοναδική λέξη με μήκος $n=0$.

Υποθέτουμε τώρα επαγωγικά ότι ισχύουν και οι τρεις άνω ισοδυναμίες για κάθε λέξη $w$ με ${\left\vert{w}\right\vert} \le n-1$.

Έστω τώρα $w$ μια λέξη με μήκος $n$. Αποδεικνύουμε την πρώτη ισοδυναμία: $w \in L(S) \Longleftrightarrow A(w)=B(w)$.

$w \in L(S) \Longrightarrow A(w) = B(w)$
Αφού $w \in L(S)$ υπάρχει μια ακολουθία παραγωγών της $G_1$ που αρχίζει από το $S$ και καταλήγει στη $w$. Αν το πρώτο γράμμα της $w$ είναι $a$ τότε στην πρώτη παραγωγή αναγκαστικά χρησιμοποιείται ο κανόνας $S \to a B$. Αυτό συνεπάγεται ότι $w = a x$ όπου $x$ είναι μια λέξη για την οποία ισχύει $x \in L(B)$, και ${\left\vert{x}\right\vert} \le n-1$. Από την επαγωγική υπόθεση έπεται ότι $B(x) = A(x)+1$ και συνεπώς $A(w) = B(w)$. Ομοίως, αν το πρώτο γράμμα της $w$ είναι $b$ τότε ο πρώτος κανόνας παραγωγής από το $S$ στο $w$ είναι αναγκαστικά ο $S \to b A$, άρα $w = b y$, με $y \in L(A)$ και ${\left\vert{y}\right\vert}=n-1$. Από την επαγωγική υπόθεση $A(y) = B(y)+1$ από το οποίο προκύπτει $A(w) = B(w)$.

$A(w) = B(w) \Longrightarrow w \in L(S)$
Αν το πρώτο γράμμα της $w$ είναι $a$ τότε $w = a x$ με $A(x) = B(x)-1$, και ${\left\vert{x}\right\vert}=n-1$. Από την επαγωγική υπόθεση προκύπτει ότι $x \in L(B)$, άρα υπάρχει τρόπος να παράγουμε το $x$ από το μη τερματικό σύμβολο $B$. Αρχίζοντας τότε από το $S$, εφαρμόζουμε τον κανόνα παραγωγής $S \to a B$ και ακολούθως παράγουμε από το $B$ το $x$. Συνολικά έχουμε παραγάγει έτσι το $w$ από το $S$ δείχνοντας σε αυτή την περίπτωση $w \in L(S)$. Ομοίως, αν το πρώτο γράμμα της $w$ είναι το $b$ τότε γράφεται $w = b y$ με ${\left\vert{y}\right\vert}=n-1$ και $A(y) = B(y)+1$, άρα, με την επαγωγική υπόθεση, ισχύει $y \in L(A)$. Για να παραγάγουμε λοιπόν τη $w$ από το $S$ ξεκινούμε εφαρμόζοντας τον κανόνα $S \to b A$, και ακολούθως παράγουμε από το $A$ το $y$, παίρνοντας έτσι τελικά το $w$.

Εδώ έχουμε δείξει το επαγωγικό βήμα για την πρώτη ισοδυναμία.

Δείχνουμε τώρα το επαγωγγικό βήμα για την ισοδυναμία $w \in L(A) \Longleftrightarrow A(w) = B(w)+1$. Προσέξτε ότι εδώ υπάρχει ασυμμετρία στην απόδειξη όσον αφορά το ρόλο που παίζει το $a$ και το $b$ ως πρώτο γράμμα της λέξης $w$.

$w \in L(A) \Longrightarrow A(w) = B(w)+1$
Έστω ότι το πρώτο γράμμα της λέξης $w$ είναι το $a$. Τότε αναγκαστικά η πρώτη παραγαγωγή από το $A$ στο $w$ είναι η $A \to a S$, οπότε $w = a x$ με ${\left\vert{x}\right\vert}=n-1$ και αναγκαστικά τότε το $x$ πρέπει να είναι παραγόμενο από το $S$, άρα $x \in L(S)$ και από την επαγωγική υπόθεση $A(x) = B(x)$, από το οποίο προκύπτει ότι $A(w) = B(w)+1$.

Αν το πρώτο γράμμα της $w$ είναι το $b$ τότε ο πρώτος κανόνας που εφαρμόζεται στην παραγωγή της $w$ από το $A$ είναι αναγκαστικά ο $A \to b A A$, οπότε έχουμε $w = b x_1 x_2$ όπου $x_1, x_2 \in L(A)$, και, φυσικά, ${\left\vert{x_1}\right\vert}, {\left\vert{x_2}\right\vert} \le n-1$. Από την επαγωγική υπόθεση τώρα προκύπτει ότι $A(x_1) = B(x_1)+1$ και $A(x_2) = B(x_2) +1$, από τα οποία προκύπτει φυσικά ότι $A(w) = B(w)+1$.

$A(w) = B(w)+1 \Longrightarrow w \in L(A)$
Αν το πρώτο γράμμα της $w$ είναι το $a$ τότε $w = a x$ με $A(x) = B(x)$, ${\left\vert{x}\right\vert}=n-1$, οπότε από την επαγωγική υπόθεση προκύπτει $x \in L(S)$. Παράγοντας τώρα από το $A$ με τον κανόνα παραγωγής $A \to a S$ και συνεχίζοντας παράγοντας από το $S$ το $x$, καταλήγουμε σε μια ακολουθία παραγωγής του $w$ από το $A$, δηλ. $w \in L(A)$.

Αν το πρώτο γράμμα της $w$ είναι το $b$ τότε $w = b x$ με ${\left\vert{x}\right\vert}=n-1$ και $A(x) = B(x)+2$. Ισχύει όμως το παρακάτω Λήμμα.

Λήμμα 9.1   Αν για μια λέξη $x\in{\left\{{a,b}\right\}}^*$ ισχύει $A(x) = B(x)+2$ τότε το $x$ σπάει ως $x = x_1 x_2$ όπου $A(x_1) = B(x_1)+1$ και $A(x_2) = B(x_2) +1$.

Άσκηση 9.4   Δείξτε το Λήμμα 9.1.

Οπότε η λέξη $x$ σπάει σε δυο κομμάτια $x_1$ και $x_2$.$x = x_1 x_2$, με μήκος το πολύ $n-2$ η καθε μία και με $A(x_i) = B(x_i)+1$.$i=1,2$. Από την επαγωγική υπόθεση έχουμε τώρα $x_1, x_2 \in L(A)$. Για να παραγάγουμε λοιπόν από το $A$ τη λέξη $w$ αρχίζουμε με τον κανόνα παραγωγής $A \to b A A$ και ακολούθως αναπτύσσουμε το πρώτο $A$ σε $x_1$ και το δεύτερο σε $x_2$, πετυχαίνοντας έτσι συνολικά μια παραγωγή της $w$ από το $A$.

Παραλείπουμε την απόδειξη του επαγωγικού βήματος για την τρίτη ισοδυναμία μια και αυτή είναι εντελώς παρόμοια με τη δεύτερη ισοδυναμία, με τους ρόλους των $a$.$b$ και $A$.$B$ εναλλαγμένους. $\qedsymbol$