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)$, αφού είναι πλέον σίγουρο ότι όσο και να συνεχίσει δε θα βρει άλλη. Αυτό το σκοπό, και για τα δύο ερωτήματα που μας απασχολούν, εξυπηρετεί το παρακάτω θεώρημα, που είναι ουσιαστικά πόρισμα του Λήμματος Άντλησης.

Θεώρημα 8.1   Αν $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$. $\qedsymbol$

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

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

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

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

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

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

$$\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. Όλα αυτά γίνονται αλγοριθμικά. $\qedsymbol$