7.9 Κλειστότητα κανονικών γλωσσών κάτω από απλές πράξεις

Από τον ορισμό των κανονικών εκφράσεων και των γλωσσών είναι φανερό ότι αν $L_1$ και $L_2$ είναι κανονικές γλώσσες τότε κανονική είναι και η $L_1 \cup L_2$ όπως και η γλώσσα $L_1^*$. Δεν είναι όμως καθόλου προφανές από τον ορισμό των κανονικών εκφράσεων το αν η συμπληρωματική γλώσσα

$$L_1^c = {\left\{{w \in \Sigma^*:  w \notin L_1}\right\}}$$

είναι κανονική. Γίνεται όμως και αυτό φανερό αν χρησιμοποιήσουμε το Θεώρημα 7.3 που λέει ότι μια γλώσσα είναι κανονική αν και μόνο αν υπάρχει ένα DFA που την αναγνωρίζει. Έστω λοιπόν ότι το DFA $M$ αναγνωρίζει τη γλώσσα $L_1$. Φτιάνχουμε ένα DFA $M'$ από το $M$ κρατώντας τις ίδιες καταστάσεις, αλφάβητο, αρχική κατάσταση και ακμές του $M$ αλλά κάνουμε όλες τις τελικές καταστάσεις του $M$ μη τελικές και όλες τις μη τελικές καταστάσεις του $M$ τις κάνουμε τελικές στο $M'$. (Εδώ πρέπει να είμαστε λίγο προσεκτικοί και να δουλεύουμε στο μορφή του $M$ που δε χρησιμοποιεί συντομογραφία, αλλά που ικανοποιεί την αρχική απαίτηση για DFA, ότι δηλ. για κάθε κατάσταση και για κάθε γράμμα του αλφαβήτου υπάρχει ακριβώς μια ακμή.) Είναι φανερό τώρα ότι μια λέξη γίνεται δεκτή στο $M'$ αν και μόνο αν δε γίνεται δεκτή στο $M$, άρα το $M'$ είναι ένα DFA για τη γλώσσα $L_1^c$.

Είναι τώρα εύκολο να δείξουμε ότι και η γλώσσα $L_1 \cap L_2$ είναι κανονική. Αρκεί να δείξουμε ότι το συμπλήρωμά της είναι, και

$$(L_1 \cap L_2)^c = L_1^c \cup L_2^c,$$

και από αυτά που είπαμε προηγουμένως προκύπτει ο ισχυρισμός.

Ορισμός 7.20   Αντικατάσταση (substitution) σε ένα αλφάβητο $\Sigma$ είναι μια οποιαδήποτε αντιστοίχιση των γραμμάτων του αλφαβήτου σε γλώσσες πάνω από το $\Sigma$, μια οποιαδήποτε συνάρτηση δηλ.

$$f: \Sigma \to 2^{\Sigma^*},$$

μια συνάρτηση δηλ. που παίρνει τιμές τυχόντα υποσύνολα του $\Sigma^*$. Αν για κάθε $\alpha\in\Sigma$ η γλώσσα $f(a)$ είναι κανονική, τότε και η αντικατάσταση ονομάζεται κανονική.

Έχοντας μια αντικατάσταση $f: \Sigma \to 2^{\Sigma^*}$ μπορούμε να επεκτείνουμε το πεδίο ορισμού της από γράμματα του $\Sigma$ σε λέξεις του $\Sigma^*$. Αν $w = \alpha_1 \cdots \alpha_n$, $\alpha_i\in\Sigma$, είναι μια λέξη, τότε ορίζουμε (χρησιμοποιούμε το ίδιο σύμβολο $f$ για να συμβολίσουμε και την επεκτεταμένη συνάρτηση)

$$f(w) = f(\alpha_1)\cdots f(\alpha_n),$$

η γλώσσα δηλ. που προκύπτει από τη συγκόλληση των γλωσσών $f(\alpha_1),\ldots,f(\alpha_n)$.

Αν $L$ είναι μια γλώσσα ορίζουμε ως συνήθως

$$f(L) = \bigcup_{w \in L} f(w).$$

Θεώρημα 7.4   Αν $L$ κανονική, και η αντικατάσταση $f$ είναι κανονική, τότε η $f(L)$ είναι κανονική γλώσσα.

Απόδειξη. (Σχέδιο απόδειξης.)

Αφού η $L$ είναι κανονική τότε προκύπτει ως γλώσσα μιας κανονικής έκφρασης $r$. Είναι εύκολο να δούμε (αλλά δεν το κάνουμε με λεπτομέρεια εδώ) ότι η γλώσσα $f(L)$ είναι ακριβώς αυτή που προκύπτει αν τροποποιήσουμε την έκφραση $r$ αντικαθιστώντας κάθε γράμμα $\alpha$ που εμφανίζεται στην $r$ με μια κανονική έκφραση για τη γλώσσα $f(\alpha)$. Άρα η γλώσσα $f(L)$ δίδεται από κανονική έκφραση, άρα είναι κανονική. $\qedsymbol$

Άσκηση 7.32   Αποδείξτε το Θεώρημα 7.4 ακολουθώντας τη «συνταγή» του σχεδίου απόδειξης που δόθηκε. Μπορείτε για παράδειγμα να χρησιμοποιήσετε επαγωγή ως προς το μήκος μιας κανονικής έκφρασης της κανονικής γλώσσας $L$.

Ορισμός 7.21   Μια αντικατάσταση $f$ λέγεται ομομορφισμός αν για κάθε $\alpha\in\Sigma$ η γλώσσα $f(\alpha)$ είναι μονοσύνολο.

Επειδή κάθε πεπερασμένο σύνολο λέξεων είναι κανονική γλώσσα (από τον ορισμό του τι είναι κανονική γλώσσα) από το προηγούμενο θεώρημα έπεται ότι οι ομομορφισμοί διατηρούν την κανονικότητα των γλωσσών.

Ορισμός 7.22   Αν $f$ είναι ομομορφισμός και $L$ είναι μια γλώσσα, η αντίστροφη ομομορφική εικόνα της $L$ είναι η γλώσσα

$$f^{-1}(L) = {\left\{{w\in\Sigma^*:   f(w) \in L}\right\}}.$$

Θεώρημα 7.5   Αν $f$ ομομορφισμός και $L$ κανονική γλώσσα τότε και η $f^{-1}(L)$ είναι κανονική.

Απόδειξη. Έστω $M$ ένα DFA που αναγνωρίζει την $L$. Φτιάχνουμε DFA $M'$ ως εξής: κρατάμε ίδιες καταστάσεις και αρχικές και τελικές καταστάσεις με το $M$ και ορίζουμε μόνο νέα συνάρτηση μετάβασης ως εξής: αν $q$ είναι μια κατάσταση του $M$ και $\alpha\in\Sigma$ ορίζουμε

$$\delta_{M'}(q, \alpha) = \delta_M(q, f(\alpha)).$$

Μεταβαίνουμε δηλ. στο $M'$ σε εκείνη την κατάσταση όπου θα καταλήγαμε αν στο $M$ ξεκινάγαμε από την κατάσταση $q$ και ακολουθούσαμε τη λέξη $f(\alpha)$. Είναι φανερό ότι η λέξη $w$ γίνεται αποδεκτή από το $M'$ αν και μόνο αν η λέξη $f(w)$ γίνεται αποδεκτή από το $M$, άρα το DFA αναγνωρίζει τη γλώσσα $f^{-1}(L)$, οπότε αυτή είναι κανονική. $\qedsymbol$

Άσκηση 7.33   Αν $L$ είναι κανονική γλώσσα τότε και η γλώσσα

$$L^R = {\left\{{x \in \Sigma^*:  x^R \in L}\right\}}$$

είναι κανονική. Με $x^R$ συμβολίζουμε τη λέξη $x$ με τα γράμματά της σε ανάποδη σειρά. Π.χ. $011^R = 110$.

Υπόδειξη: Δουλέψτε πάνω σε μια κανονική έκφραση για την $L$.