Μη προσβάσιμες καταστάσεις

Ένα πεπερασμένο αυτόματο μπορεί να έχει καταστάσεις στις οποίες δεν είναι δυνατό να φτάσουμε. Τέτοιες καταστάσεις τις λέμε μη προσβάσιμες καταστάσεις. Συνήθως θέλουμε να τις αφαιρούμε, επειδή απλώς περιπλέκουν άσκοπα όλο το αυτόματο.

Παράδειγμα μη προσβάσιμων καταστάσεων

Έστω αυτό το αυτόματο:

Βλέπουμε ότι, ό,τι κι αν κάνουμε, στην κατάσταση q₃ δεν θα φτάσουμε ποτέ, γιατί δεν οδηγεί σε αυτήν καμία μετάβαση. Για την κατάσταση q₃ λέμε λοιπόν ότι είναι μη προσβάσιμη. Ερώτηση – θα ήταν προσβάσιμη η κατάσταση q₃, αν οδηγούσε σε αυτήν κάποια μετάβαση από άλλη κατάσταση; Αν φέρναμε ακμή από μία από τις καταστάσεις q₀, q₁, q₂, q₅, τότε θα ήταν προσβάσιμη. Αν προσθέταμε έναν ακόμη κόμβο και φέρναμε μετάβαση από αυτόν…

…τότε φυσικά και οι δύο καταστάσεις q₃ και q₄ θα ήταν μη προσβάσιμες.

Ορισμός της μη προσβάσιμης κατάστασης

Πρώτα ορίζουμε την προσβάσιμη κατάσταση. Έστω ένα πεπερασμένο αυτόματο A = ⟨Q, Σ, δ, q₀, F⟩. Λέμε ότι μια κατάσταση q ∈ Q είναι προσβάσιμη, αν υπάρχει λέξη w ∈ Σ^∗ τέτοια ώστε

$$⟨q_0,w⟩{\mapsto }^{\ast }⟨q,\epsilon ⟩.$$

Μια κατάσταση q ∈ Q είναι μη προσβάσιμη, αν δεν είναι προσβάσιμη.

Πώς να αφαιρέσουμε τις μη προσβάσιμες καταστάσεις

Αν ένα αυτόματο έχει ήδη κάποιες μη προσβάσιμες καταστάσεις, είναι σκόπιμο να τις αφαιρέσουμε. Κατασκευάζουμε έτσι ένα ισοδύναμο αυτόματο A′ = ⟨Q′, Σ, δ′, q₀, F′⟩, που δεν θα έχει μη προσβάσιμες καταστάσεις.

Θα κατασκευάζουμε επαναληπτικά το σύνολο των προσβάσιμων καταστάσεων. Ξεκινάμε με το σύνολο S₀ = {q₀}, επειδή η αρχική κατάσταση είναι σίγουρα προσβάσιμη. Το επόμενο σύνολο κατασκευάζεται ως εξής:

$$S_i=\{r\mid \delta (q,a)=r\text{ για κάποια }q\in S_{i-1},a\in \mathrm{\Sigma }\}\cup S_{i-1}$$

Με απλά λόγια, το σύνολο S₀ είναι πάντα δεδομένο, το σύνολο S₁ το κατασκευάζουμε παίρνοντας όλες τις καταστάσεις του συνόλου S₀ και βρίσκοντας πού οδηγούν οι μεταβάσεις για όλα τα σύμβολα του Σ. Αυτές τις καταστάσεις τις ενώνουμε με το αρχικό σύνολο καταστάσεων S₀. Με την ίδια διαδικασία βρίσκουμε το σύνολο S₂ και τα επόμενα. Προφανώς ισχύει S_{i − 1} ⊆ S_i.

Το σύνολο των προσβάσιμων καταστάσεων μπορούμε τότε να το πάρουμε ως εξής:

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$$

Μπορεί να φαίνεται περίεργο ότι προσπαθούμε να ενώσουμε άπειρα σύνολα S_i, όμως το αυτόματο περιέχει μόνο πεπερασμένο πλήθος καταστάσεων. Αυτό σημαίνει ότι κάποια στιγμή τα σύνολα S_j και S_{j + 1} και όλα τα επόμενα θα είναι ίδια, οπότε και μετά την ένωση άπειρων συνόλων μπορούμε να πάρουμε πεπερασμένο σύνολο καταστάσεων.

Ας επιστρέψουμε στο αυτόματο

και ας προσπαθήσουμε να βρούμε το σύνολο των προσβάσιμων καταστάσεων. Ξεκινάμε βάζοντας τη βασική ισότητα

$$S_0=\left\{q_0\right\}$$

Τώρα υπολογίζουμε το σύνολο S₁. Πρέπει λοιπόν να βρούμε όλες τις μεταβάσεις από την κατάσταση q₀ και τις καταστάσεις προορισμού τους να τις προσθέσουμε στο σύνολο S₀. Επειδή ισχύει q₀ → ^a q₁ και q₀ → ^bq₂, το σύνολο S₁ θα περιέχει επιπλέον τις καταστάσεις q₁ και q₂:

$$S_1=\{q_0,q_1,q_2\}$$

Στη συνέχεια κατασκευάζουμε το σύνολο S₂. Κοιτάμε πού μπορούμε να φτάσουμε από τις καταστάσεις q₀, q₁, q₂. Η μόνη νέα κατάσταση είναι η q₅, στην οποία φτάνουμε από την κατάσταση q₁:

$$S_2=\{q_0,q_1,q_2,q_5\}$$

Έπειτα κατασκευάζουμε το σύνολο S₃. Μπορούμε από τις καταστάσεις q₀, q₁, q₂, q₅ να φτάσουμε σε κάποια νέα κατάσταση; Δεν μπορούμε, άρα το σύνολο S₃ θα περιέχει τα ίδια στοιχεία με το S₂:

$$S_3=\{q_0,q_1,q_2,q_5\}$$

Επειδή S₂ = S₃, ισχύει και S₃ = S₄ = S₅ = … Αν ενώσουμε όλα τα S_i, παίρνουμε το σύνολο S₂, γιατί κανένα άλλο στοιχείο δεν θα προστεθεί πια σε κανένα επόμενο σύνολο.

Το σύνολο των προσβάσιμων καταστάσεων του αυτομάτου είναι λοιπόν ίσο με {q₀, q₁, q₂, q₅}. Τις μη προσβάσιμες καταστάσεις τις παίρνουμε με απλή διαφορά συνόλων:

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$$

Το σύνολο των μη προσβάσιμων καταστάσεων του αυτομάτου μας είναι το {q₃, q₄}. Αφαιρούμε από το αυτόματο A όλες τις μη προσβάσιμες καταστάσεις και όλες τις μεταβάσεις που περιείχαν κάποια μη προσβάσιμη κατάσταση. Δηλαδή το ισοδύναμο αυτόματο χωρίς μη προσβάσιμες καταστάσεις A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ για το αυτόματο A = ⟨Q, Σ, δ, q₀, F⟩ το ορίζουμε ως εξής:

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
• $F^{\prime }=F\cap Q^{\prime }=F\cap \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$

Πηγές

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools