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$, ξεκινώντας πάντα από την αρχική του κορυφή.

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

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

Ορισμός 8.1  

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

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

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

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

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

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

Υπόδειξη: Εξετάστε την $R_M$.

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

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

Απόδειξη. $1 \Rightarrow 2$
Αν η $L$ είναι κανονική τότε αναγνωρίζεται από ένα DFA $M$ και το ζητούμενο είναι η Άσκηση 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.3)

  
  

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

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

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

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

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