5.6 Πα, 11/10/02: Κανονικές εκφράσεις και γλώσσες. Σχέση με αυτόματα.

5.6.1 Κανονικές εκφράσεις και οι γλώσσες τους

Θα δώσουμε κατ' αρχήν ένα αναδρομικό ορισμό για το τι είναι μια κανονική έκφραση (regular expression) και το ποια γλώσσα παριστάνει.

Ορισμός 3   Οι παρακάτω εκφράσεις είναι κανονικές. Με $L(\cdot)$ συμβολίζουμε τη γλώσσα μιας έκφρασης.

• $\emptyset$, και $L(\emptyset) = \emptyset$
• $\epsilon$, και $L(\epsilon) = {\left\{{\epsilon}\right\}}$
• $\alpha$, για κάθε $\alpha\in\Sigma$, και $L(\alpha) = {\left\{{\alpha}\right\}}$.

Επίσης, αν $r$ και $s$ είναι κανονικές εκφράσεις τότε και οι ακόλουθες είναι επίσης κανονικές

1. $(r+s)$, και $L((r+s)) = L(r) \cup L(s)$
2. $(rs)$, και $L((rs)) = L(r)L(s)$ (συγκόλληση των δύο γλωσσών)
3. $(r^*)$, και $L((r^*)) = L(r)^*$.

Μια γλώσσα $L$ λέγεται κανονική αν υπάρχει κανονική έκφραση $r$ με $L = L(r)$.

Παρατηρήσεις: Αν μπορούμε να παρελείψουμε τις παρανθέσεις χωρίς να αλλάξουμε το νόημα τότε το κάνουμε αυτό. Λαμβάνουμε υπόψιν ότι τη μεγαλύτερη προτεραιότητα έχει ο εκθέτης $*$, μετά έρχεται η συγκόλληση και τέλος η πρόσθεση. Αν $r$ είναι μια κανονική έκφραση τότε χρησιμοποιούμε επίσης τη συντομογραφία $r^+$ αντί για $rr^*$.

Τα παρακάτω είναι παραδείγματα κανονικών εκφράσεων και των γλωσσών τους.

Κανονική έκφραση	Αντίστοιχη γλώσσα
$00$	${\left\{{00}\right\}}$
$(0+1)^*$	Όλες οι λέξεις πάνω από το $\Sigma = {\left\{{0, 1}\right\}}$
$(0+1)^*00(0+1)^*$	Όλες οι λέξεις πάνω από το $\Sigma = {\left\{{0, 1}\right\}}$ που έχουν δύο διαδοχικά μηδενικά
$(1+10)^*$	Ότι αρχίζει με 1 και δεν έχει διαδοχικά 0
$(0+\epsilon)(1+10)^*$	Ότι δεν έχει διαδοχικά 0
$0^*1^*2^*$	Λέξεις όπου τα 0 έρχονται πριν τα 1 κι αυτά πριν τα 2.

Άσκηση 5.6.1   Γράψτε κανονικές εκφράσεις για τις ακόλουθες γλώσσες:

1. Λέξεις που δεν περιέχουν τη μορφή 101.
2. Λέξεις όπου όλες οι εμφανίσεις διαδοχικών 0 συμβαίνουν πριν από οποιαδήποτε εμφάνιση διαδοχικών 1.

Άσκηση 5.6.2   Περιγράψτε τις γλώσσες που ορίζονται από τις κανονικές εκφράσεις:

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

Άσκηση 5.6.3   Δείξτε τις παρακάτω ταυτότητες όπου $r,s,t$ είναι κανονικές εκφράσεις.

1. $r+s=s+r$
2. $(r+s)+t = r+(s+t)$
3. $(rs)t = r(st)$
4. $r(s+t) = rs+rt$
5. $(r+s)t = rt+st$
6. $\emptyset^* = \epsilon$
7. $(r^*)^* = r^*$
8. $(\epsilon+r)^* = r^*$
9. $(r^*s^*)^*=(r+s)^*$

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

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

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

Παρατηρείστε ότι δεν ξεκαθαρίζουμε τι είδους αυτόματο μια και είναι όλα ισοδύναμα.

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

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

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

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

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

Στο Σχήμα 15 βλέπουμε στα (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.$$ (4)

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

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

Για $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}^k$ είναι πεπερασμένα σύνολα από σύμβολα του $\Sigma$ ή το γράμμα $\epsilon$. Κάθε ένα όμως από αυτά είναι κανονική γλώσσα άρα είναι τέτοια και η $R_{i,j}^k$.

Όσον αφορά το επαγωγικό βήμα, αν υποθέσουμε ότι οι $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}.$$ (5)

Γιατί ισχύει η (5);

Είναι φανερό ότι η γλώσσα $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$ όως φαίνεται στο Σχήμα 16.

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

Μια τέτοια λέξη αντιστοιχεί σε ένα μονοπάτι πάνω στο DFA που σίγουρα ``πατάει'' πάνω στην κορυφή $q_k$, ενδεχομένως και πάνω από μία φορά (στο Σχήμα 16 πατάει δύο φορές). Αν ονομάσουμε $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}.$$

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

Άσκηση 5.6.4   Κατασκευάστε 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))^*$