5.3 Τρ, 1/10/02: Σχέσεις, ισοδυναμίες, μεταβατική κλειστότητα. Ντετερμινιστικά αυτόματα

5.3.1 Σχέσεις ορισμένες σε σύνολα

Ορισμός 2   Σχέση $R$ πάνω σε ένα σύνολο $A$ είναι ένα οποιοδήποτε υποσύνολο $R \subseteq A \times A$.

Γράφουμε συνήθως $x R y$ αντί για $(x,y) \in R$.

Παραδείγματα

1. $A = {\mathbf R}$, $R = {\left\{{(x,y)\in{\mathbf R}^2: x \le y}\right\}}$. Αντί για $x R y$ γράφουμε κατά παράδοση $x \le y$.
2. $A = {\mathbf Z}$, $m\in{\mathbf Z}$, $R = {\left\{{(x,y)\in{\mathbf Z}^2: m \vert y-x}\right\}}$. Αντί για $x R y$ γράφουμε $x \sim_m y$ και διαβάζουμε ``το $x$ είναι ισουπόλοιπο $\bmod m$ με το $y$''. Με λίγη σκέψη βλέπουμε ότι αυτό συμβαίνει αν και μόνο αν τα $x$ και $y$ αφήνουν το ίδιο υπόλοιπο διαιρούμενα με $m$.
3. $A = {\mathbf Z}$, $x R y$ αν και μόνο αν $2 \vert x-y$ ή $3 \vert x-y$.

Μια σχέση $R$ λέγεται ανακλαστική αν $x R x$ για κάθε $x \in A$, συμμετρική αν $x R y \Rightarrow y R x$ και, τέλος, μεταβατική αν $(x R y \& y R z ) \Rightarrow x R z$. Στα παραπάνω παραδείγματα η σχέση $\le$ είναι ανακλαστική και μεταβατική αλλά όχι συμμετρική, η σχέση $\sim_m$ έχει και τις τρεις ιδιότητες και το τελευταίο παράδειγμα είναι ανακλαστική και συμμετρική σχέση αλλά όχι μεταβατική.

Άσκηση 5.3.1   Έστω $G$ κατευθυνόμενο γράφημα με σύνολο κορυφών $G$. Ορίζουμε τη σχέση $R$ στο $V$: $u   R   v$ αν υπάρχει μονοπάτι πάνω στο $G$ που ξεκινά από το $u$ και καταλήγει στο $v$. Είναι η σχέση $R$ ανακλαστική, συμμετρική, μεταβατική;

Άσκηση 5.3.2   Γράφουμε $x R y$ για δυο ακεραίους $x$ και $y$ αν $x \mid y$ (ο $x$ διαιρεί τον $y$). Δείξτε ότι η σχέση $R$ είναι μεταβατική.

5.3.2 Μεταβατική κλειστότητα $R^+$ μιας σχέσης $R$

Παρατηρείστε ότι αν δύο σχέσεις $R_1$ και $R_2$ είναι ανακλαστικές τότε και η $R_1 \cap R_2$ είναι, και ομοίως διατηρείται από τις τομές η συμμετρική και η μεταβατική ιδιότητα (αποδείξτε το αυτό). Έστω λοιπόν για μια σχέση $R$ η σχέση που συμβολίζουμε με $R^+$ και ορίζεται ως η τομή όλων των μετεβατικών σχέσεων $S \supseteq R$. Είναι προφανές ότι η $R^+$ είναι μια μεταβατική σχέση υποσύνολο κάθε μεταβατικής σχέσης που περιέχει την $R$. Υπό αυτή την έννοια είναι η ελάχιστη μεταβατική σχέση που περιέχει την $R$ και την ονομάζουμε μεταβατική κλειστότητα ή μεταβατική θήκη της $R$.

Υπάρχει και ένας άλλος τρόπος να δούμε τη σχέση $R^+$. Το να μην είναι μια σχέση μεταβατική σημαίνει ότι υπάρχουν δύο ζεύγη $(a, b), (b,c) \in R$ αλλά $(a, c) \notin R$. Για να μετατρέψουμε λοιπόν τη σχέση $R$ στη σχέση $R^+$, την ``ελάχιστη μεταβατική σχέση που περιέχει την $R$'', προσθέτουμε στη σχέση τα ζευγάρια αυτά που λείπουν, μέχρι να μη χρειάζεται να προσθέσουμε άλλα. Φυσικά, αυτή η διαδικασία που μόλις περιγράψαμε, για να έχει νόημα, πρέπει κάποια στιγμή να τελειώσει. Και αυτό δεν είναι πρόβλημα για σχέσεις $R$ που είναι πεπερασμένες (π.χ. όλες οι σχέσεις ορισμένες σε πεπερασμένο σύνολο $A$) αλλά όταν θέλουμε να ορίσουμε το $R^+$ για άπειρες σχέσεις $R$ πρέπει να χρησιμοποιήσουμε τον ορισμό που δώσαμε πιο πάνω με την, εν δυνάμει, άπειρη τομή.

Παράδειγμα.
Δείχνουμε τώρα ότι η μεταβατική κλειστότητα της σχέσης 3, παραπάνω, είναι η πλήρης σχέση στους ακεραίους, δηλ. κάθε δύο ακέραιοι σχετίζονται μεταξύ τους. Πράγματι, αν πούμε $R$ τη σχέση 3, τότε $x   R^+   x$ για κάθε $x \in ZZ$ αφού το 0 διαρείται από το 2 (και το 3). Επίσης, δείχνουμε με επαγωγή ως πρός το θετικό αριθμό $k$ ότι $x   R^+   x+k$ και $x+k   R^+   x$. Δείχνουμε μόνο το πρώτο μια και το δεύτερο είναι εντελώς αντίστοιχο. Για $k=1$ πρέπει να δείξουμε ότι $x   R^+   x+1$. Αλλά $x   R   x+3$ (διαφορά 3) και $x+3   R   x+1$ (διαφορά 2) και επειδή $R \subseteq R^+$ έχουμε επίσης $x   R^+   x+3, x+3   R^+   x+1$ και από τη μεταβατικότητα της $R^+$ έχουμε $x   R^+   x+1$.

Υποθέτουμε τώρα $x   R^+   x+k$ για κάποιο $k$ και για κάθε $x$ και πάμε να δείξουμε $x   R^+   x+k+1$. Αλλά έχουμε $x   R^+   x+k$ και από το βήμα 1 έχουμε $x+k-1   R^+   x+k$ (διαφορά 1). Από μεταβατικότητα έχουμε $x   R^+   x+k+1$, που τελειώνει την απόδειξη.

Άσκηση 5.3.3   Για δυο ακεραίους $x$ και $y$ γράφουμε $x R y$ αν το ${\left\vert{x-y}\right\vert}$ ισούται με 15 ή 13. Ποια η μεταβατική κλειστότητα της σχέσης $R$;

5.3.3 Ντετερμινιστικά Αυτόματα - Εισαγωγή

Ένα Ντετερμινιστικό Αυτόματο (Deterministic Finite Automaton ή DFA) είναι ουσιαστικά ένα κατευθυνόμενο γράφημα, του οποίου οι κορυφές $Q$ ονομάζονται καταστάσεις (states) και από κάθε κορυφή φεύγει ακριβώς μια ακμή για κάθε γράμμα του αλφαβήτου $\Sigma$. Υπάρχει μια διακεκριμένη κορυφή $q_0$, η αρχική κορυφή και ένα μη-κενό σύνολο $F$ από τελικές κορυφές.

Δείτε π.χ. ένα τέτοιο αυτόματο στην παρακάτω εικόνα.

Σχήμα 3. Ένα απλό ντετερμινιστικό αυτόματο

Τυπικά λοιπόν ένα ντετερμινιστικό αυτόματο είναι μια πεντάδα

$$(Q, \Sigma, \delta, q_0, F)$$

όπου

• $Q$ είναι ένα πεπερασμένο σύνολο καταστάσεων
• $\Sigma$ είναι ένα πεπερασμένο αλφάβητο
• $\delta$ είναι η συνάρτηση μετάβασης (transition function) με πεδίο ορισμού το $Q \times \Sigma$ και πεδίο τιμών το $Q$
• $q_0\in Q$ είναι μια από τις καταστάσεις που ονομάζεται αρχική
• $F \subseteq Q$ είναι το σύνολο των τελικών καταστάσεων.

Στο αυτόματο που φαίνεται στο σχήμα παραπάνω έχουμε $Q = {\left\{{A, B, C, D}\right\}}$, $\Sigma = {\left\{{0, 1}\right\}}$, $q_0 = A$, $F = {\left\{{C}\right\}}$.

Για να μιλήσουμε για τη συνάρτηση μετάβασης $\delta$ θα πρέπει πρώτα να αναφερθούμε στον τρόπο ``λειτουργίας'' του αυτομάτου. Ένα αυτόματο χρησιμεύει για να αναγνωρίζει, όπως λέμε, μια γλώσσα $L \subseteq \Sigma^*$. Η διαδικασία αναγνώρισης είναι η εξής.

Έστω λέξη $w \in \Sigma^*$, $w = w_1\ldots w_n$, μήκους $n$ ( $w_i \in \Sigma$).

• Το αυτόματο αρχίζει τη λειτουργία του στην αρχική κατάσταση $q_0$.
• Διαβάζει έπειτα τα γράμματα της λέξης ένα προς ένα, από τα αριστερά προς τα δεξιά πάντα. Πρώτο διαβάζεται το γράμμα $w_1$ και τελευταίο το $w_n$.
• Μόλις διαβάσει το γράμμα $\alpha\in\Sigma$ και ευρισκόμενο στην κατάσταση $q$ το αυτόματο μεταβαίνει στην κατάσταση $r$ αν και μόνο αν η ακμή $q \to r$ έχει ετικέτα (label) ίση με $\alpha$. Για κάθε κατάσταση του αυτομάτου και κάθε γράμμα του αλφαβήτου υπάρχει εξ ορισμού ακριβώς μια ακμή που ξεκινά από την κατάσταση αυτή και έχει ετικέτα αυτό το γράμμα. Ισχύει τότε για τη συνάρτηση μετάβασης $\delta(q, \alpha) = r$, χρησιμεύει δηλ. η συνάρτηση μετάβασης για να μας προσδιορίσει σε ποια κατάσταση πάει το αυτόματο αν βρίσκεται σε μια δεδομένη κατάσταση και διαβάσει ένα συγκεκριμένο γράμμα. Όλη η συνδεσμολογία του αυτομάτου δηλ. είναι κωδικοποιημένη στη συνάρτηση $\delta$.
• Αφού διαβάσει το αυτόματο το τελευταίο γράμμα της λέξης και κάνει την τελευταία του μετάβαση δηλώνει ότι αποδέχεται τη λέξη αν και μόνο αν βρίσκεται σε τελική κατάσταση, σε μια κατάσταση δηλ. του συνόλου $F$. Αλλιώς η λέξη απορρίπτεται.
• Το σύνολο των λέξεων που αποδέχεται το αυτόματο ονομάζεται η γλώσσα που αναγνωρίζει το αυτόματο.

Ποια είναι η γλώσσα $L$ που αναγνωρίζεται από το αυτόματο της εικόνας 3;

Δε θέλει και πολλή σκέψη για να πειστούμε ότι στην $L$ ανήκουν ακριβώς εκείνες οι λέξεις του ${\left\{{0,1}\right\}}^*$ που έχουν περιττό αριθμό από 0 και περιττό αριθμό από 1. Για να το δούμε αυτό παρατηρούμε ότι οποτεδήποτε το αυτόματο βρίσκεται σε μια από τις δύο αριστερές καταστάσεις το πλήθος των μηδενικών που έχει διαβάσει είναι άρτιο. Αυτό γίνεται γιατί αυτή η πρόταση ισχύει προφανέστατα τη χρονική στιγμή 0, αφού τότε δεν έχει διαβάσει κανένα μηδενικό και βρίσκεται στην αρχική κατάσταση $A$ που είναι στην αριστερή μεριά. Οποτεδήποτε διαβάσει επίσης κάποιο μηδενικό το αυτόματο αλλάζει μεριά και διατηρείται έτσι η ιδιότητα αυτή. Ομοίως επιχειρηματολογώντας βλέπουμε ότι το αυτόματο βρίσκεται σε μια από τις δύο πάνω καταστάσεις ($A$ και $B$) αν και μόνο αν έχει διαβάσει άρτιο αριθμό από 1. Έτσι, το να είναι το αυτόματο στην κατάσταση $C$ (τελική) σημαίνει ότι έχει δει περιττό αριθμό από ένα και περιττό από μηδέν, αφού η $C$ είναι κάτω (περιττοί άσσοι) και δεξιά (περιττά μηδενικά).

Αν π.χ. θελήσουμε να έχουμε ένα αυτόματο που θα αναγνωρίζει ακριβώς εκείνες τις λέξεις του ${\left\{{0,1}\right\}}^*$ που έχουν περιττά μηδενικά ή άρτιους άσσους η μόνη αλλαγή που χρειάζεται να κάνουμε στην περιγραφή του αυτομάτου είναι να αλλάξουμε το σύνολο $F$ των τελικών καταστάσεων και να το θέσουμε ίσο με το ${\left\{{A, B, C}\right\}}$ (βεβαιωθείτε ότι το καταλαβαίνετε αυτό).

Άσκηση 5.3.4   Σχεδιάστε ένα DFA που να αναγνωρίζει εκείνες τις λέξεις πάνω από το $\Sigma = {\left\{{0, 1}\right\}}$ που έχουν άρτιο πλήθος άσσων και πλήθος μηδενικών που είναι πολλαπλάσιο του 3.

Άσκηση 5.3.5   Σχεδιάστε ένα DFA που αναγνωρίζει εκείνες τις λέξεις πάνω από το $\Sigma = {\left\{{0, 1}\right\}}$ που αρχίζουν από 11011.