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

Οι κανονικές εκφράσεις που θα δούμε σε αυτή την παράγραφο είναι ένας διαφορετικός τρόπος περιγραφής μιας γλώσσας που αναγνωρίζεται από ένα DFA. Είναι μάλιστα ένας αρκετά πιο συνοπτικός και διαισθητικός τρόπος να περιγράψει κανείς μια τέτοια γλώσσα και γι' αυτό το λόγο είναι ένας τρόπος που χρησιμοποιείται πολύ στην πράξη.

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

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

• $\emptyset$, και $L(\emptyset) = \emptyset$ (η κενή γλώσσα, που δεν περιέχει καμία λέξη)
• $\epsilon$, και $L(\epsilon) = {\left\{{\epsilon}\right\}}$ (η γλώσσα που περιέχει μόνο μια λέξη, την κενή λέξη $\epsilon$)
• $\alpha$, για κάθε $\alpha\in\Sigma$, και $L(\alpha) = {\left\{{\alpha}\right\}}$.

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

1. $(r)$, και $L((r)) = L(r)$.
2. $(r+s)$, και $L((r+s)) = L(r) \cup L(s)$,
3. $(rs)$, και $L((rs)) = L(r)L(s)$,
4. $(r^*)$, και $L((r^*)) = L(r)^*$.

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

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

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

Κανονική έκφραση	Αντίστοιχη γλώσσα
$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.

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

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

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

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

Άσκηση 7.28   Δείξτε τις παρακάτω ταυτότητες όπου $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)^*$