Ελαχιστοποίηση αυτομάτου

Με την ελαχιστοποίηση αυτομάτου εννοούμε την εύρεση ενός ισοδύναμου αυτομάτου που περιέχει τον ελάχιστο δυνατό αριθμό καταστάσεων. Ακόμη και ένα αυτόματο που δεν περιέχει καμία περιττή κατάσταση μπορεί να απλοποιηθεί περαιτέρω.

Παράδειγμα

Ας πάρουμε αυτό το αυτόματο:

το αυτόματο αποδέχεται μόνο τις λέξεις 01 και 11. Είναι προφανές ότι υπάρχει απλούστερο αυτόματο με τρεις καταστάσεις, που αποδέχεται την ίδια γλώσσα. Οι καταστάσεις q₁ και q₂ μπορούν να συγχωνευθούν σε μία νέα κατάσταση {q₁, q₂} και οι μεταβάσεις που οδηγούσαν στις καταστάσεις q₁ ή q₂ θα οδηγούν στη νέα κατάσταση, και το ίδιο ισχύει για τις μεταβάσεις που ξεκινούσαν από τις q₁ και q₂. Παίρνουμε αυτό το αυτόματο:

Αυτό το αυτόματο φανερά αποδέχεται την ίδια γλώσσα με το προηγούμενο και ταυτόχρονα έχει λιγότερες καταστάσεις.

Ισοδυναμία καταστάσεων

Έστω ένα αυτόματο A = ⟨Q, Σ, δ, q₀, F⟩. Ορίζουμε τη γλώσσα της κατάστασης q ∈ Q, που τη συμβολίζουμε L(q), ως

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Δηλαδή αλλάζουμε την αρχική κατάσταση του αυτομάτου A από την q₀ στην q και υπολογίζουμε τη γλώσσα που αποδέχεται αυτό το αυτόματο. Με άλλα λόγια, στη γλώσσα L(q) ανήκουν όλες οι λέξεις w για τις οποίες στο αυτόματο A φτάνουμε από την κατάσταση q με τη λέξη w σε τελική κατάσταση του αυτομάτου. Αν επιστρέψουμε στο προηγούμενο αυτόματο, ισχύει L(q₁) = {1}.

Λέμε ότι δύο διαφορετικές καταστάσεις q₁ και q₂ είναι ισοδύναμες, αν ισχύει

$L (q_{1}) = L (q_{2})$

Τι σημαίνει αυτό; Αν οι καταστάσεις q₁, q₂ είναι ισοδύναμες, τότε αν τις κάνουμε αρχικές καταστάσεις του αυτομάτου, θα παράγουν την ίδια γλώσσα. Με άλλα λόγια: αν το αυτόματο βρεθεί στη διαμόρφωση ⟨q₁, w⟩ και στη διαμόρφωση ⟨q₂, w⟩, τότε πρέπει και στις δύο περιπτώσεις να αποδεχτεί ή και στις δύο περιπτώσεις να απορρίψει.

Αν επιστρέψουμε στο προηγούμενο αυτόματο: οι καταστάσεις q₁ και q₂ είναι ισοδύναμες, γιατί αν βρισκόμαστε στην κατάσταση q₁, μπορούμε να αποδεχτούμε τη λέξη εισόδου μόνο όταν το αδιάβαστο μέρος της λέξης είναι ίσο με 1. Το ίδιο ισχύει αν βρισκόμαστε στην κατάσταση q₂.

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

Πώς να βρούμε τις ισοδύναμες καταστάσεις

Ποιες καταστάσεις σίγουρα δεν θα είναι ισοδύναμες; Αν πάρουμε μια τελική και μια μη τελική κατάσταση, σίγουρα δεν θα είναι ισοδύναμες, επειδή η γλώσσα της τελικής κατάστασης είναι διαφορετική από τη γλώσσα της μη τελικής – η τελική κατάσταση σίγουρα αποδέχεται τη λέξη ε, η μη τελική όχι. Τη διαδικασία θα τη δούμε αμέσως σε παράδειγμα. Έστω λοιπόν αυτό το αυτόματο:

Ξεκινάμε δημιουργώντας δύο σύνολα καταστάσεων

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Τώρα δημιουργούμε τον πίνακα μεταβάσεων και κρατάμε την πληροφορία για τις ομάδες S₁ και S₂:

$\begin{array}{ccccc} ομάδα & κατάσταση & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Τώρα τροποποιούμε τον πίνακα έτσι ώστε, αντί να γράφουμε απευθείας σε ποιες καταστάσεις πηγαίνουμε για το δεδομένο σύμβολο, να σημειώνουμε μόνο την ομάδα στην οποία πηγαίνουμε. Για παράδειγμα από την κατάσταση q₃ για το 0 φτάνουμε στην κατάσταση q₅, που είναι στην ομάδα S₂. Αντί για q₅ γράφουμε λοιπόν στον πίνακα S₂:

$\begin{array}{ccccc} ομάδα & κατάσταση & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Τώρα χωρίζουμε περαιτέρω και τις δύο ομάδες. Στις ίδιες ομάδες βάζουμε πάντα καταστάσεις που για όλα τα σύμβολα πηγαίνουν στις ίδιες ομάδες. Για παράδειγμα οι καταστάσεις q₃ και q₆ δεν θα είναι στην ίδια ομάδα, επειδή ούτε για το 0 ούτε για το 1 δεν πηγαίνουν στην ίδια ομάδα. Αντίθετα, οι καταστάσεις q₁ και q₂ θα είναι στην ίδια ομάδα, επειδή και οι δύο καταστάσεις δεν έχουν μετάβαση για το 0 και πηγαίνουν και οι δύο για το 1 στην ομάδα S₁. Δημιουργούμε έτσι νέες ομάδες:

$\begin{array}{ccccc} ομάδα & κατάσταση & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Σε κάθε ομάδα έχουμε τις ίδιες μεταβάσεις. Τις νέες ομάδες τις σημειώνουμε και πάλι βρίσκουμε σε ποια από αυτές τις νέες ομάδες πηγαίνουν οι καταστάσεις:

$\begin{array}{ccccc} ομάδα & κατάσταση & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

Σε αυτό το σημείο χωρίζουμε ξανά τις ομάδες. Βλέπουμε όμως ότι δεν μπορούμε να κάνουμε κανέναν περαιτέρω χωρισμό, θα παίρναμε τις ίδιες ομάδες – επειδή οι καταστάσεις q₁ και q₂ έχουν μεν ίδιες μεταβάσεις ως προς τις ομάδες, αλλά είναι ήδη στην ίδια ομάδα και καμία άλλη κατάσταση στην ομάδα S₄ δεν υπάρχει. Ο αλγόριθμος εύρεσης ισοδύναμων καταστάσεων έχει τελειώσει. Από κάθε ομάδα μας αρκεί να διαλέξουμε μία κατάσταση, τις υπόλοιπες τις διαγράφουμε και όλες οι μεταβάσεις που οδηγούσαν στις διαγραμμένες καταστάσεις θα οδηγούν στη μία κατάσταση που διαλέξαμε.

Μπορούμε έτσι να αποφασίσουμε ότι το νέο μας αυτόματο θα έχει τις καταστάσεις q₃, q₆, q₀, q₁, q₄ και τις καταστάσεις q₂ και q₅ τις αφαιρούμε. Όλες οι μεταβάσεις που οδηγούσαν στην q₂ θα οδηγούν τώρα στην q₁ και όλες οι μεταβάσεις που οδηγούσαν στην q₅ θα οδηγούν στην q₄:

Διαδικασία ελαχιστοποίησης αυτομάτου

Αφαιρούμε τις μη προσβάσιμες καταστάσεις,
αφαιρούμε τις περιττές καταστάσεις,
αφαιρούμε τις ισοδύναμες καταστάσεις.

Πηγές

Κεφάλαια: Μη προσβάσιμες καταστάσεις, Περιττές καταστάσεις, Ελαχιστοποίηση αυτομάτου

« Προηγούμενο: Περιττές καταστάσεις

Επόμενο: Κλειστότητα κανονικών γλωσσών »