7.8 Κανονικότητα γλωσσών των αυτομάτων

Η βασική πρόταση είναι η ακόλουθη.

Θεώρημα 7.3   (Κανονικότητα γλωσσών των αυτομάτων) Μια γλώσσα είναι κανονική αν και μόνο αν αναγνωρίζεται από κάποιο αυτόματο.

Παρατήρηση 7.11   Παρατηρήστε ότι στο Θεώρημα 7.3 δεν ξεκαθαρίζουμε για τι είδους αυτόματο μιλάμε. Έχουμε όμως ήδη αποδείξει ότι κάθε $\epsilon$-NFA είναι ισοδύναμο με κάποιο NFA και κάθε NFA με κάποιο DFA. Αυτό σημαίνει ότι μια γλώσσα αναγνωρίζεται από ένα αυτόματο κάποιου είδους από τα τρία αν και μόνο αν αναγνωρίζεται από αυτόματο οποιουδήποτε είδους.

Απόδειξη. Θα δείξουμε ότι (α) Κάθε κανονική γλώσσα αναγνωρίζεται από κάποιο $\epsilon$-NFA, και (β) Η γλώσσα που αναγνωρίζει κάθε DFA είναι κανονική.

(α) Χρησιμοποιούμε επαγωγή ως προς το μήκος της κανονικής έκφρασης $r$ που παράγει τη γλώσσα. Αν πρόκειται για μια από τις εκφράσεις $\emptyset$.$\epsilon$ ή $a$, με $a \in \Sigma$, πολύ εύκολα φτιάχνουμε αυτόματα που τις αναγνωρίζουν όπως φαίνεται στο παρακάτω Σχήμα 7.12.

Σχήμα 7.12: Τα $\epsilon$-NFA για τις εκφράσεις $\emptyset$ (a), $\epsilon$ (b) και $a$ (c)

Αν τώρα έχουμε μια έφραση $x$ του τύπου $r+s$.$rs$ η $r^*$, τότε τα μήκη των $r$ και $s$ είναι αυστηρά μικρότερα του ${\left\vert{x}\right\vert}$, άρα μπορούμε να υποθέσουμε επαγωγικά ότι έχουμε κάποια αυτόματα $M$ και $N$ που αναγνωρίζουν τις γλώσσες $L(r)$ και $L(s)$. Χρησιμοποιούμε τα $M$ και $N$ σα μαύρα κουτιά και μας ενδιαφέρει μόνο να «βλέπουμε» απ' έξω τις αρχικές και τελικές τους καταστάσεις.

Σχήμα 7.13: (a) Αυτόματο για $r$, (b) για $s$, (c) για $r+s$, (d) για $rs$, (e) για $r^*$

Στο Σχήμα 7.13 βλέπουμε στα (a) και (b) τα αυτόματα $M$ και $N$ που αντιστοιχούν στις εκφράσεις $r$ και $s$. Στα (c), (d) και (e) βλέπουμε πως αυτά συνδυάζονται ώστε να φτιάξουν αυτόματα για τις γλώσσες $r+s$.$rs$ και $r^*$.

Στο (c) ορίζουμε μια νέα αρχική κορυφή και την ενώνουμε με $\epsilon$-ακμές με τις δύο αρχικές κορυφές των $M$ και $N$. Οι τελικές καταστάσεις παραμένουν οι ίδιες.

Στο (d) αρχική κορυφή είναι αυτή του $M$ του οποίου οι τελικές καταστάσεις συνδέονται με $\epsilon$-ακμές με την αρχική του $N$. Τελικές καταστάσεις του συμπλέγματος είναι αυτές του $N$.

Στο (e) οι τελικές καταστάσεις του $M$ συνδέονται με $\epsilon$-ακμές με την αρχική κατάσταση του $M$. Αρχικές και τελικές καταστάσεις παραμένουν οι ίδιες.

(β) Έστω DFA $M = (Q, \Sigma, \delta, q_1, F)$, όπου $Q = {\left\{{q_1,\ldots,q_n}\right\}}$. Ορίζουμε για $i,j=1,\ldots,n$, $k=0,\ldots,n$, τις γλώσσες $R_{i,j}^k$ να είναι εκείνες οι λέξεις του $\Sigma^*$ που είναι τέτοιες ώστε αν ξεκινήσουμε από την κορυφή $q_i$ και τις ακολουθήσουμε τότε φτάνουμε στην κορυφή $q_j$ χωρίς να χρησιμοποιήσουμε κορυφή $q_l$ με $l>k$.

Είναι φανερό ότι

$$L(M) = \bigcup_{q_j \in F} R_{1,j}^n.$$ (7.3)

Με άλλα λόγια, αποδεκτές γίνονται εκείνες οι λέξεις που μας επιτρέπουν να φτάσουμε, ξεκινώντας από την αρχική κορυφή $q_1$, σε κάποια από τις κορυφές $q_j \in F$, χωρίς κανένα περιορισμό ως προς τις ενδιάμεσες κορυφές (επειδή ο άνω δείκτης είναι $n$, και, ούτως ή άλλως, δεν υπάρχουν κορυφές $q_l$, με $l>n$.

Θα δείξουμε με επαγωγή ως προς το $k$ ότι οι γλώσσες $R_{i,j}^k$ είναι όλες κανονικές. Άρα κανονική είναι και η $L(M)$ αφού με βάση την (7.3) είναι πεπερασμένη ένωση από κανονικές γλώσσες, και η ένωση δύο κανονικών γλωσσών είναι εξ ορισμού κανονική.

Για $k=0$ τώρα, παρατηρούμε ότι η απαίτηση, στον ορισμό της $R_{i,j}^k$ όσον αφορά το ποιες κορυφές δεν πρέπει να χρησιμοποιηθούν είναι ιδιαίτερα αυστηρή, αφού η συνθήκη $l>0$ ισχύει για κάθε κορυφή $q_l\in Q$. Άρα έχουμε

$$R_{i,j}^0 = \left\{ \begin{array}{ll} {\left\{{\alpha\in\Sig... ...}} \cup {\left\{{\epsilon}\right\}} & (i=j) \end{array}\right.$$

Αυτό σημαίνει ότι οι γλώσσες $R_{i,j}^0$ είναι πεπερασμένα σύνολα από σύμβολα του $\Sigma$ ή το γράμμα $\epsilon$. Κάθε ένα όμως από αυτά είναι κανονική γλώσσα άρα είναι τέτοια και η $R_{i,j}^0$.

Όσον αφορά το επαγωγικό βήμα, αν υποθέσουμε ότι οι $R_{i,j}^{k-1}$ είναι όλες κανονικές τότε το ίδιο συνάγουμε και για τις $R_{i,j}^k$ αφού παρατηρήσουμε ότι ισχύει η αναδρομική σχέση

$$R_{i,j}^k = R_{i,k}^{k-1} (R_{k,k}^{k-1})^* R_{k,j}^{k-1} \cup R_{i,j}^{k-1}.$$ (7.4)

Γιατί όμως ισχύει η (7.4);

Είναι φανερό ότι η γλώσσα $R_{i,j}^k$ είναι υπερσύνολο της $R_{i,j}^{k-1}$, αφού ο περιορισμός $l\le k$, στον ορισμό της $R_{i,j}^k$, γίνεται ασθενέστερος (ισχύει πιο συχνά) όσο μεγαλώνει το $k$. Ποιες είναι όμως εκείνες οι λέξεις που ανήκουν στο σύνολο $R_{i,j}^k$ αλλά όχι στο $R_{i,j}^{k-1}$, οι λέξεις με άλλα λόγια της (συνολοθεωρητικής) διαφοράς $R_{i,j}^k \setminus R_{i,j}^{k-1}$; Είναι ακριβώς εκείνες οι λέξεις που οδηγούν από την κατάσταση $q_i$ στην $q_j$, χωρίς να «πατούν» σε κορυφή $q_l$.$l>k$, αλλά που πατούν τουλάχιστον μια φορά στην κορυφή $q_k$ όως φαίνεται στο Σχήμα 7.14.

Σχήμα 7.14: Ένα μονοπάτι στο DFA που αντιστοιχεί σε λέξη του $R_{i,j}^k \setminus R_{i,j}^{k-1}$

Μια τέτοια λέξη αντιστοιχεί σε ένα μονοπάτι πάνω στο DFA που σίγουρα «πατάει» πάνω στην κορυφή $q_k$, ενδεχομένως και πάνω από μία φορά (στο Σχήμα 7.14 πατάει δύο φορές). Αν ονομάσουμε $w$ μια τέτοια λέξη, και ονομάσουμε $\sigma$ το πρόθεμα της $w$ που αντιστοιχεί στο μονοπάτι από το $q_i$ στο $q_k$, που δεν πατάει στην $q_k$, και $\tau$ το επίθεμα της $w$ γαι το μονοπάτι $q_k \to q_j$ που δεν πατάει στην $q_k$, τότε η $w$ γράφεται

$$w = \sigma v_1 \cdots v_t \tau,$$

όπου οι λέξεις $v_1,\ldots,v_t$ αντιστοιχούν σε μονοπάτια που αρχίζουν και τελειώνουν από το $q_k$, χωρίς να πατούν στο $q_k$. Είναι δηλ. $\sigma\in R_{i,k}^{k-1}$, $v_l \in R_{k,k}^{k-1}$, $l=1,\ldots,t$, και $\tau \in R_{k,j}^{k-1}$, έχουμε άρα δείξει τον εγκλεισμό

$$R_{i,j}^k \setminus R_{i,j}^{k-1} \subseteq R_{i,k}^{k-1} (R_{k,k}^{k-1})^* R_{k,j}^{k-1}.$$

Ο αντίστροφος εγκλεισμός είναι ακόμη πιο εύκολος και παραλείπεται. $\qedsymbol$

Άσκηση 7.29   Κατασκευάστε DFA για τις κανονικές εκφράσεις:

1. $10+(0+11)0^*1$
2. $01\left(((10)^*+111)^*+0\right)^*1$
3. $((0+1)(0+1))^* + ((0+1)(0+1)(0+1))^*$

Άσκηση 7.30   Δώστε μια κανονική έκφραση για τη γλώσσα που αναγνωρίζει το αυτόματο του Σχήματος 7.15.

Σχήμα 7.15: Το Σχήμα για την Άσκηση 7.30

Άσκηση 7.31   Δώστε μια κανονική έκφραση για τη γλώσσα που αναγνωρίζει το αυτόματο του Σχήματος 7.16.

Σχήμα 7.16: Το Σχήμα για την Άσκηση 7.31