Περιττές καταστάσεις

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

Παράδειγμα περιττών καταστάσεων

Έστω αυτό το πεπερασμένο αυτόματο:

Βλέπουμε ότι μόλις βρεθούμε στις καταστάσεις q₄ ή q₅, δεν θα καταφέρουμε ποτέ να φτάσουμε σε μία από τις τελικές καταστάσεις q₁ ή q₂. Τέτοιες καταστάσεις είναι λοιπόν περιττές και μπορούμε απλώς να τις αφαιρέσουμε, παίρνοντας έτσι ένα νέο αυτόματο, που όμως θα ήταν ισοδύναμο· θα αποδεχόταν την ίδια γλώσσα. Μετά τη διαγραφή των περιττών καταστάσεων το αυτόματο θα έμοιαζε ως εξής:

Θα αποδεχόταν μάλιστα την ίδια γλώσσα. Υπάρχουν όμως περιπτώσεις που είναι σκόπιμο να έχουμε κάποιες περιττές καταστάσεις – για παράδειγμα όταν κατασκευάζουμε πλήρες αυτόματο.

Ορισμός της περιττής κατάστασης

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

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

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

Υποθέτουμε ότι στην είσοδο έχουμε αυτόματο A = ⟨Q, Σ, δ, q₀, F⟩, που είναι ήδη χωρίς μη προσβάσιμες καταστάσεις. Θα βρίσκουμε σταδιακά τις καταστάσεις που οδηγούν σε τελικές καταστάσεις και μετά τις καταστάσεις που οδηγούν σε καταστάσεις που οδηγούν σε τελικές καταστάσεις και ούτω καθεξής. Έτσι παίρνουμε το σύνολο όλων των καταστάσεων που δεν είναι περιττές. Στην αρχή θέτουμε S₀ = F. Θα κατασκευάζουμε τα επόμενα σύνολα S_i για i ∈ ℕ^∗ με αυτόν τον κανόνα:

$$S_i=\{q\in Q\mid \mathrm{\exists }a\in \mathrm{\Sigma }:\delta (q,a)\in S_{i-1}\}\cup S_{i-1}$$

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

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

Και το σύνολο των περιττών καταστάσεων ως

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

Με άλλα λόγια: αν ισχύει S_i = S_{i + 1}, τότε το σύνολο Q ∖ S_i περιέχει τις περιττές καταστάσεις. Τη διαδικασία θα την παρουσιάσουμε σε αυτό το αυτόματο:

Πρώτα θέτουμε την ισότητα S₀ = {q₁, q₂}. Στη συνέχεια κατασκευάζουμε το σύνολο S₁ προσθέτοντας στο σύνολο S₀ όλες τις καταστάσεις που οδηγούν σε μία από τις καταστάσεις του συνόλου S₀. Προσθέτουμε έτσι τις καταστάσεις q₀ και q₃, επειδή από την q₀ οδηγεί μετάβαση στην q₁ και από την q₃ οδηγεί μετάβαση στην q₂. Παίρνουμε S₁ = {q₀, q₁, q₂, q₃}. Επειδή S₀ ≠ S₁, συνεχίζουμε.

Κατασκευάζουμε το σύνολο S₂. Ψάχνουμε λοιπόν όλες τις καταστάσεις από τις οποίες μπορούμε να φτάσουμε στο S₁ και που δεν είναι ακόμη στο S₁. Είναι μία μόνο, η q₆, από την οποία μπορούμε να φτάσουμε στην κατάσταση q₃. Παίρνουμε S₂ = {q₀, q₁, q₂, q₃, q₆}. Επειδή S₁ ≠ S₂, συνεχίζουμε.

Κατασκευάζουμε το σύνολο S₃. Υπάρχει κάποια νέα κατάσταση, από την οποία μπορούμε να φτάσουμε σε κάποια από τις καταστάσεις του S₂; Δεν υπάρχει, από τις καταστάσεις q₄ και q₅ δεν μπορούμε να φτάσουμε σε καμία από τις καταστάσεις του S₂ και οι υπόλοιπες καταστάσεις είναι ήδη στο S₂. Ισχύει λοιπόν S₃ = {q₀, q₁, q₂, q₃, q₆}. Επειδή S₂ = S₃, ο αλγόριθμος τελειώνει και το σύνολο S₂ είναι το σύνολο των καταστάσεων που δεν είναι περιττές. Το σύνολο {q₄, q₅} είναι το σύνολο των καταστάσεων που είναι περιττές.

Τυπικά, το νέο ισοδύναμο αυτόματο χωρίς περιττές καταστάσεις κατασκευάζεται ως εξής. Έχουμε το αυτόματο A = ⟨Q, Σ, δ, q₀, F⟩ και κατασκευάζουμε γι' αυτό ένα ισοδύναμο αυτόματο A′ = ⟨Q′, Σ, δ′, q₀, F⟩ χωρίς περιττές καταστάσεις.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a), αν δ(q, a) ∈ Q′, αλλιώς το δ′(q, a) δεν ορίζεται

Πηγές

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