5.8 Τρ, 29/10/02, Πα 1/11/02: Αλγόριθμοι για DFA. Θεώρημα Myhill-Nerode

5.8.1 Πότε ένα DFA αναγνωρίζει κενή ή άπειρη γλώσσα

Δοθέντος ενός DFA $M$ καλούμαστε να αποφασίσουμε με αλγοριθμικό τρόπο για το αν

1. Υπάρχει έστω και μία λέξη που αναγνωρίζεται από το $M$,
2. Υπάρχουν άπειρες λέξεις που αναγνωρίζονται από το $M$.

Και στις δύο περιπτώσεις καλούμαστε να απαντήσουμε απλώς με ένα ναι ή όχι, και δε ζητούμε να βρούμε μία ή περισσότερες (πόσο μάλλον άπειρες) λέξεις για να αποδείξουμε τα λεγόμενά μας.

Πρέπει δηλ. να βρούμε ένα τρόπο να απαντήσουμε αν η γλώσσα του $M$ είναι κενή ή όχι, και αν είναι άπειρη ή όχι ( $L(M)=\emptyset$; και ${\left\vert{L(M)}\right\vert}=\infty$;). Και πρέπει ο τρόπος απόφασης να είναι αλγοριθμικός, δηλ. να μπορούμε να γράψουμε ένα πρόγραμμα στον υπολογιστή το οποίο, όποια και να είναι η απάντηση, να μπορεί να τη βρίσκει. Αυτό σημαίνει ότι σε κάθε περίπτωση (όποια και να είναι η απάντηση) πρέπει το πρόγραμμα αυτό (α) να τελειώσει και (β) να δώσει τη σωστή απάντηση.

Η απαίτηση για το (β) είναι προφανής στον περισσότερο κόσμο αλλά δεν είναι ίσως φανερό τι εννοούμε με το (α). Είναι λοιπόν χρήσιμο να τονίσουμε ότι ο ακόλουθος αλγόριθμος για να αποφασίσουμε το ερώτημα $L(M)=\emptyset$ δεν είναι αποδεκτός:

Με τον υπολογιστή μας απαριθμούμε όλες τις λέξεις του $\Sigma^*$ ως εξής. Πρώτα απαριθμούμε όλες τις λέξεις μήκους 0 (υπάρχει μόνο μία, η κενή λέξη $\epsilon$), μετά απαριθμούμε τις λέξεις μήκους 1 (υπάρχουν τόσες όσα και α γράμματα του $\Sigma$, δηλ. το πλήθος τους είναι ${\left\vert{\Sigma}\right\vert}$), μετά τις λέξεις μήκους 2 (υπάρχουν ακριβώς ${\left\vert{\Sigma}\right\vert}^2$ τέτοιες), κ.ο.κ. Με αυτό τον τρόπο απαρίθμησης διανύουμε όλες τις λέξεις του $\Sigma^*$, χωρίς να ξαχνάμε καμιά. Για κάθε λέξη θα έρθει κάποτε η σειρά να την εξετάσουμε. Παράλληλα με την απαρίθμηση προγραμματίζουμε τον υπολογιστή μας να εξετάζει κάθε μια από τις αριθμούμενες λέξεις για το αν περνάνε από το $M$ ή όχι. Αν έστω και μια βρεθεί που να αναγνωρίζεται από το $M$ τότε σταματάέι ο αλγόριθμος και απαντά ΝΑΙ (στο ερώτημα αν $L(M)=\emptyset$), αλλιώς συνεχίζει.

Είναι φανερό ότι αυτή η μέθοδος κάνει, κατά κάποιο τρόπο, μισή δουλειά, μια και δεν είναι ποτέ δυνατό να απαντήσει ΟΧΙ, αφού δεν ξέρουμε, όσες λέξεις και να έχουμε δει μέχρι στιγμής, για το αν υπάρχει λέξη της $L(M)$ που να βρίσκεται παρακάτω στην αρίθμησή μας, π.χ. να έχει μεγαλύτερο μήκος απ' ό,τι έχουμε εξετάσει μέχρι στιγμής. Αν η απάντηση στο ερώτημα είναι ΝΑΙ τότε, αργά ή γρήγορα, ο αλγόριθμός μας θα απαντήσει ΝΑΙ, δε συμβαίνει όμως το ίδιο και με το ΟΧΙ.

Πώς θα μπορούσε κάπως να διορθωθεί ο αλγόριθμος που μόλις περιγράψαμε;

Αν είχαμε ένα τρόπο, με δεδομένη την περιγραφή του $M$, να ξέρουμε πόσο μεγάλη (το πολύ) είναι η μικρότερη σε μήκος λέξη της $L(M)$, αν μια τέτοια λέξη υπάρχει, τότε θα προγραμματίζαμε τον υπολογιστή μας να σταματάει την απαρίθμηση όταν έχει περάσει αυτό το φράγμα και δεν έχει βρει ακόμη λέξη της $L(M)$, αφού είναι πλέον σίγουρο ότι όσο και να συνεχίσει δε θα βρει άλλη. Αυτό το σκοπό, και για τα δύο ερωτήματα που μας απασχολούν, εξυπηρετεί το παρακάτω θεώρημα, που είναι ουσιαστικά πόρισμα του Λήμματος Άντλησης.

Θεώρημα 6   Αν $M$ είναι ένα DFA με $n$ καταστάσεις τότε

1. $L(M)\neq \emptyset$ αν και μόνο αν υπάρχει $w \in L(M)$ με ${\left\vert{w}\right\vert}<n$.
2. ${\left\vert{L(M)}\right\vert}=\infty$ αν και μόνο αν υπάρχει $w \in L(M)$ με $n \le {\left\vert{w}\right\vert} < 2n$.

Απόδειξη. 1. Αν υπάρχει $w \in L(M)$ με ${\left\vert{w}\right\vert}<n$ τότε προφανώς $L(M)\neq \emptyset$. Αντίστροφα, έστω $L(M)\neq \emptyset$ και $w \in L(M)$ έχευ ελάχιστο μήκος. Αν ${\left\vert{w}\right\vert}\ge n$ τότε, από το Λήμμα Άντλησης, υπάρχει σπάσιμο $w = uvz$ με $v \neq \epsilon$ τέτοιο ώστε για κάθε $i\ge 0$ έχουμε $uv^iz \in L(M)$. Για $i=0$ παίρνουμε $uz \in L(M)$, η οποία όμως λέξη έχει μήκος μικρότερο της $w = uvz$ η οποία είχε εξ αρχής υποτεθεί ότι έχει ελάχιστο μήκος, πράγμα άτοπο, άρα ${\left\vert{w}\right\vert}<n$.

2. Αν υπάρχει $w \in L(M)$ με $n \le {\left\vert{w}\right\vert} < 2n$ τότε (χρησιμοποιώντας μόνο την ανισότητα $n \le {\left\vert{w}\right\vert}$) από το Λήμμα Άντλησης το $w$ σπάει σε $w = uvz$, $v \neq \epsilon$, έτσι ώστε οι λέξεις $uv^iz$, $i\ge 0$, ανήκουν όλες στην $L(M)$. Αλλά αυτές είναι άπειρες το πλήθος, άρα ${\left\vert{L(M)}\right\vert}=\infty$. Αντίστροφα, έστω ${\left\vert{L(M)}\right\vert}=\infty$ και υποθέσουμε ότι δεν υπάρχει λέξη $w$ με μήκος από $n$ έως και $2n-1$, ας πάρουμε $w$ να είναι λέξη με ελάχιστο μήκος μεγαλύτερο ή ίσο του $2n$ (τέτοιες λέξεις υπάρχουν αναγκαστικά αφού η $L(M)$ έχει υποτεθεί άπειρη γλώσσα). Το Λήμμα Άντλησης εφαρμόζεται και πάλι αφού ${\left\vert{w}\right\vert} \ge 2n \ge n$ άρα η λέξη $w$ γράφεται $w = uvz$, με ${\left\vert{uv}\right\vert}\le n$ και $v \neq \epsilon$ και $uv^iz \in L(M)$ (για $i\ge 0$). Άρα $uz \in L(M)$ και αφού ${\left\vert{uvz}\right\vert}\ge 2n$ και ${\left\vert{v}\right\vert}\le n$ συμπεραίνουμε ότι ${\left\vert{uz}\right\vert}\ge n$, άρα (έχουμε υποθέσει ότι δεν υπάρχουν λέξεις στην $L(M)$ με μήκος από $n$ έως και $2n-1$) ${\left\vert{uz}\right\vert}\ge 2n$, πράγμα που αντιφάσκει με το ότι η $w$ έχει ελάχιστο μήκος ανάμεσα στις λέξεις της $L(M)$ με μήκος τουλάχιστον $2n$.
$\Box$

Είμαστε τώρα σε θέση να δείξουμε το ακόλουθο αποτέλεσμα.

Θεώρημα 7   Τα ακόλουθα ερωτήματα είναι αλγοριθμικά αποφασίσιμα:

1. Αναγνωρίζει το DFA $Μ$ μια μη κενή γλώσσα;
2. Αναγνωρίζει το DFA $Μ$ μια άπειρη γλώσσα;
3. Αναγνωρίζουν τα DFA $Μ_1$ και $M_2$ την ίδια γλώσσα;

Απόδειξη. 1. Απαριθμούμε όλες τις λέξεις μήκους μέχρι και $n$ με γράμματα από το $\Sigma$ (υπάρχουν ακριβώς $1+{\left\vert{\Sigma}\right\vert}+{\left\vert{\Sigma}\right\vert}^2+\cdots+{\left\vert{\Sigma}\right\vert}^n$ τέτοιες λέξεις) και τις ελέγχουμε όλες αν περνάνε από το αυτόματο $M$. Αν έστω και μια από αυτές αναγνωρίζεται τότε απαντάμε ΝΑΙ, αλλιώς απαντάμε ΟΧΙ. Η μέθοδος είναι σωστή με βάση το Θεώρημα 6.1.

2. Απαριθμούμε όλες τις λέξεις μήκους από $n$ έως και $2n-1$ με γράμματα από το $\Sigma$. Αν έστω και μια από αυτές αναγνωρίζεται τότε απαντάμε ΝΑΙ, αλλιώς απαντάμε ΟΧΙ. Η μέθοδος είναι σωστή με βάση το Θεώρημα 6.2.

3. Θέλουμε να απαντήσουμε στο ερώτημα

$$L(M_1) \neq L(M_2).$$

Η απάντηση σε αυτό είναι ΝΑΙ αν και μόνο αν η ακόλουθη γλώσσα είναι μη κενή

$$(L(M_1) \cap L(M_2)^c) \cup (L(M_1)^c \cap L(M_2)).$$ (6)

Μπορούμε όμως αλγοριθμικά να κατασκευάσουμε ένα DFA $M$ που αναγνωρίζει ακριβώς αυτή τη γλώσσα, οπότε μετά χρησιμοποιούμε τον αλγόριθμο του σκέλους 1 αυτού του Θεωρήματος για να αποφασίσουμε αν η γλώσσα της (6) είναι κανή ή όχι. Το αυτόματο $M$ κατασκευάζεται ως εξής. Παρατηρούμε ότι η (6) γράφεται

$$\left(L(M_1)^c \cup L(M_2)\right)^c \cup \left(L(M_1) \cup L(M_2)^c\right)^c$$

και ότι αυτή η έκφραση χρησιμοποιεί μόνο ενώσεις και συμπληρώματα. Αν έχουμε ένα DFA $N$ και θέλουμε να φτιάξουμε ένα DFA $N'$ για τη συμπληρωματική γλώσσα τότε απλά αλλάζουμε τις τελικές καταστάσεις του $N$ σε μη τελικές και τις μη τελικές σε τελικές. Για να φτιάξουμε ένα DFA για την ένωση δύο γλωσσών (των οποίων ξέρουμε κάποια DFA) φτιάχνουμε πρώτα ένα $\epsilon$-NFA για αυτή την ένωση και το μετατρέπουμε στη συνέχεια σε DFA. Όλα αυτά γίνονται αλγοριθμικά.
$\Box$

5.8.2 Σχέσεις ισοδυναμίας για γλώσσες και αυτόματα. Θεώρημα Myhill-Nerode

Πάνω στο σύνολο $\Sigma^*$ όλων των λέξεων ορίζονται φυσιολογικά οι εξής σχέσεις ισοδυναμίας

1. Αν $L \subseteq \Sigma^*$ είναι μια γλώσσα η σχέση $R_L$ ορίζεται ως: $x R_L y$ αν και μόνο αν για κάθε $z \in \Sigma^*$ έχουμε
   $$xz \in L \Leftrightarrow yz \in L,$$
   δηλ. τα $xz$, $yz$ είτε ανήκουν και τα δυο στην $L$ είτε κανένα.
2. Αν $M$ είναι ένα DFA τότε ορίζουμε $x R_M y$ αν και μόνο αν
   $$\delta(q_0,x) = \delta(q_0, y),$$
   όπου $q_0$ είναι η αρχική κατάσταση του $M$ και $\delta(\cdot,\cdot)$ είναη η συνάρτηση μετάβασης του $M$. Ισχύει δηλ. $x R_M y$ αν και μόνο αν το αυτόματο $M$ καταλήγει στην ίδια κορυφή αφού διαβάσει το $x$ και αφού διαβάσει το $y$, ξεκινώντας πάντα από την αρχική του κορυφή.

Άσκηση 5.8.1   Δείξτε ότι οι σχέσεις $R_L$ και $R_M$ είναι σχέσεις ισοδυναμίας.

Άσκηση 5.8.2   Δείξτε ότι η γλώσσα $L$ είναι ένωση κάποιων κλάσεων ισοδυναμίας της $R_L$ (ανεξάρτητα από το αν είναι η $L$ κανονική ή όχι). Κάθε $R_L$-κλάση δηλ. είτε περιέχεται πλήρως στην $L$ είτε δεν περιέχει λέξεις της $L$.

Ορισμός 7   Δείκτης μιας σχέσης ισοδυναμίας $R$ λέγεται ο πληθάριθμος του συνόλου των κλάσεων ιδοσυναμίας της $R$.

Άσκηση 5.8.3   Δείξτε ότι ο δείκτης της $R_M$ είναι πεπερασμένος και ίσος με το πλήθος των κορυφών του $M$ που είναι προσπελάσιμες από την αρχική κορυφή $q_0$. Μια κορυφή $v$ λέγεται προσπελάσιμη αν υπάρχει λέξη $w$ τ.ώ. $\delta(q_0, w) = v$.

Ορισμός 8   Μια σχέση $R$ ορισμένη πάνω στο $\Sigma^*$ λέγεται δεξιά αναλλοίωτη (right invariant) αν για κάθε $x, y, z \in \Sigma^*$ ισχύει

$$x R y \Rightarrow xz  R  yz.$$ (7)

Άσκηση 5.8.4   Δείξτε ότι οι σχέσεις $R_L$ και $R_M$ που ορίσαμε παραπάνω είναι δεξιά αναλλοίωτες.

Άσκηση 5.8.5   Αν $M$ είναι ένα DFA δείξτε ότι η γλώσσα $L(M)$ που αναγνωρίζει το $M$ είναι μια ένωση κλάσεων ισοδυναμίας μιας σχέσης ισοδυναμίας με πεπερασμένο δείκτη. (Υπόδειξη: Εξετάστε την $R_M$.)

Θεώρημα 8 (Θεώρημα Myhill-Nerode)   Αν $L \subseteq \Sigma^*$ τα ακόλουθα είναι ισοδύναμα:

1. Η γλώσσα $L$ είναι κανονική.
2. Η γλώσσα $L$ είναι ένωση κάποιων κλάσεων ισοδυναμίας μιας δεξιά αναλλοίωτης σχέσης ισοδυναμίας $R$ με πεπερασμένο δείκτη.
3. Η σχέση $R_L$ έχει πεπερασμένο δείκτη.

Απόδειξη.

$1 \Rightarrow 2$
Αν η $L$ είναι κανονική τότε αναγνωρίζεται από ένα DFA $M$ και το ζητούμενο είναι η Άσκηση 5.8.5.

$2 \Rightarrow 3$
Έστω ότι η γλώσσα $L$ είναι ένωση κλάσεων μιας σχέσης ισοδυναμίας $R$ που έχει πεπερασμένο δείκτη $t < \infty$. Θα δείξουμε ότι ο δείκτης της $R_L$ είναι το πολύ $t$, άρα πεπερασμένος.

Δείχνουμε κατ' αρχήν τη συνεπαγωγή $x R y \Rightarrow x R_L y$: Έστω $z \in \Sigma^*$, $xz \in L$ και $x R y$. Επειδή $R$ δεξιά αναλλοίωτη έπεται $xz R yz$. Άρα το $yz$ ανήκει στην ίδια $R$-κλάση με το $xz$. Αφού όμως $xz \in L$, και η $L$ είναι ένωση κλάσεων της $R$, ολόκληρη η $R$-κλάση του $xz$ περιέχεται στην $L$, άρα $yz \in L$. Δείξαμε δηλ. ότι $xz \in L \Rightarrow yz \in L$, και ακριβώς το ίδιο προκύπτει και η αντίστροφη συνεπαγωγή, άρα $x R_L y$, όπως θέλαμε να δείξουμε.

Η συνεπαγωγή που δείξαμε ( $x R y \Rightarrow x R_L y$) σημαίνει ότι κάθε κλάση της $R$ περιέχεται εξ ολοκλήρου σε μια κλάση της $R_L$. Πράγματι, έστω $x\in K$, όπου $K$ μια $R$-κλάση, και έστω $x \in S$, όπου $S$ η $R_L$-κλάση του $x$. Δείχνουμε τότε ότι $K \subseteq S$. Έστω λοιπόν $y \in K$. Αυτό σημαίνει $x R y$ άρα και $x R_L y$, οπότε $y \in S$.

Αφού κάθε $R$-κλάση περιέχεται σε μια $R_L$-κλάση λοιπόν δε μπορούν οι $R_L$-κλάσεις να είναι περισσότερες από τις $R$-κλάσεις, γιατι τότε θα υπήρχε κάποια $R_L$-κλάση που δε θα περιείχε καμιά $R$-κλάση και θα ήταν κενή, πράγμα που εξ ορισμού δε γίνεται.

$3 \Rightarrow 1$
Υποθέτουμε τώρα ότι η $R_L$ έχει πεπερασμένο δείκτη και δείχνουμε ότι η $L$ αναγνωρίζεται από κάποιο DFA $M$, άρα είναι κανονική. Αν $x \in \Sigma^*$ συμβολίζουμε με $[x]$ την $R_L$-κλάση ισοδυναμίας της λέξης $x$.

• Ως σύνολο καταστάσεων του αυτομάτου $M$ παίρνουμε το σύνολο $Q$ όλων των $R_L$-κλάσεων, που είναι πεπερασμένο από την υπόθεση.
• Ως αρχική κατάσταση παίρνουμε την κλάση $[\epsilon]$ της κενής λέξης.
• Τη συνάρτηση μετάβασης ορίζουμε ως εξής:

  $$\delta([x],\alpha) = [x\alpha], (\alpha\in\Sigma).$$ (8)

  
  

• Ως τελικές κορυφές παίρνουμε εκείνες τις κλάσεις της $R_L$ που περιέχονται στην $L$ (δες Άσκηση 5.8.2).

Άσκηση 5.8.6   Δείξτε ότι ο ορισμός (8) είναι ``καλός''. Αυτό σημαίνει ότι αν $K = [x] = [y]$ και εφαρμόσουμε τον (8) για να ορίσουμε την κορυφή $\delta(K, \alpha)$ τότε παίρνουμε το ίδιο αποτέλεσμα είτε χρησιμοποιήσουμε το στοιχείο $x$ στον (8) είτε το $y$.

Επαναλαμβάνοντας τον ορισμό (8) (ή εφαρμόζοντας επαγωγή στο μήκος της λέξης $w \in \Sigma^*$) βλέπουμε ότι

$$\delta([x],w) = [xw],$$

άρα $\delta([\epsilon],w)=[\epsilon w]=[w]$ που είναι τελική κατάσταση του $M$ αν και μόνο αν $w \in L$, άρα το $M$ αναγνωρίζει ακριβώς τη γλώσσα $L$.
$\Box$