Μετατροπή αυτομάτου σε κανονική έκφραση

Θα δούμε πώς μπορούμε να μετατρέψουμε οποιοδήποτε πεπερασμένο αυτόματο σε κανονική έκφραση.

Περιγραφή του αλγορίθμου

Στην είσοδο έχουμε ένα NFA A. Πρώτα το μετατρέπουμε σε GNFA. Στη δεύτερη φάση σε κάθε βήμα απαλείφουμε μία κατάσταση, τροποποιούμε σωστά τη συνάρτηση μετάβασης και επαναλαμβάνουμε, μέχρι να μείνουν μόνο δύο καταστάσεις – η αρχική και η τελική. Ανάμεσά τους θα υπάρχει μία ακμή, της οποίας η ετικέτα είναι κανονική έκφραση, και αυτή είναι το αποτέλεσμα ολόκληρου του αλγορίθμου. Όλη η διαδικασία συνίσταται λοιπόν κυρίως στην απαλοιφή μιας κατάστασης και στην επακόλουθη διόρθωση του αυτομάτου, ώστε να πάρουμε ένα ισοδύναμο αυτόματο.

Απαλοιφή μίας κατάστασης

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

όπου τα R_i είναι κάποιες κανονικές εκφράσεις. Πώς θα έμοιαζε το αυτόματο, αν απαλείφαμε την κατάσταση q_r; Μπορούμε να το φανταστούμε ως εξής: βρισκόμαστε στην κατάσταση q_i και ρωτάμε ποιες λέξεις μπορούμε να παράγουμε σε αυτό το τμήμα. Αν πάμε από την κατάσταση q_i απευθείας στην q_j, θα είναι όλες οι λέξεις που αντιστοιχούν στην κανονική έκφραση R₄.

Αν όμως πάμε στην κατάσταση q_r, μπορούμε να παράγουμε λέξεις της μορφής R₁. Στην κατάσταση q_r όμως μπορούμε να κάνουμε βρόχο με την κανονική έκφραση R₂, οπότε στην πραγματικότητα μπορούμε να παράγουμε λέξεις της μορφής $R_1\circ (R_2^{\ast })$. Και επειδή μπορούμε ακόμη να περάσουμε από την κατάσταση q_r στην q_j, προσθέτουμε στο τέλος και την κανονική έκφραση R₃. Συνολικά, με αυτή τη διαδρομή μπορούμε να πάρουμε λέξεις της μορφής $R_1\circ (R_2^{\ast })\circ R_3$.

Τώρα ξέρουμε ότι από αυτό το τμήμα του αυτομάτου μπορούν να προκύψουν λέξεις της μορφής R₄ ή της μορφής $R_1\circ (R_2^{\ast })\circ R_3$. Αυτό φυσικά μπορούμε να το γράψουμε ως κανονική έκφραση: $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Τώρα μπορούμε απλά να απαλείψουμε την κατάσταση q_r και να αφήσουμε μόνο τις δύο καταστάσεις q_i και q_j, γράφοντας στη θέση του R₄ την έκφραση που μόλις υπολογίσαμε:

Αυτή τη διαδικασία την εκτελούμε για κάθε ακμή από κάθε κατάσταση q_i προς κάποια κατάσταση q_j, συμπεριλαμβανομένων των βρόχων, δηλαδή και της περίπτωσης q_i = q_j.

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

Ο πλήρης αλγόριθμος

Στην είσοδο έχουμε ένα NFA A = ⟨Q, Σ, δ, q₀, F⟩.

1. Μετατρέπουμε το NFA A σε GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. Στη συνέχεια με το γράμμα k θα συμβολίζουμε το πλήθος των καταστάσεων του Z.
2. Αν k = 2, ο αλγόριθμος τελειώνει και στην ακμή ανάμεσα στην αρχική και την τελική κατάσταση βρίσκεται η κανονική έκφραση που ψάχνουμε.
3. Αν k>2, επιλέγουμε μια οποιαδήποτε κατάσταση q_r που είναι διαφορετική από την αρχική και την τελική, δηλαδή q_r ≠ q₀′ και q_r ≠ q_f′. Στη συνέχεια δημιουργούμε ένα νέο GNFA Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩, για το οποίο θα ισχύει: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ και για όλες τις q_i ∈ Q′′ ∖ {q_f′} και όλες τις q_j ∈ Q′′ ∖ {q₀′} ας είναι $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ όπου R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Συνέχισε με το βήμα 2.

Παράδειγμα

Έστω ότι στην είσοδο έχουμε αυτό το πεπερασμένο αυτόματο:

Πρώτα το μετατρέπουμε σε GNFA (τις περιττές ∅-μεταβάσεις δεν τις σχεδιάζουμε):

Τώρα εφαρμόζουμε το δεύτερο μέρος του αλγορίθμου και απαλείφουμε κάποιον κόμβο. Ξεκινάμε με τον κόμβο q₂. Απαλείφουμε τον κόμβο q₂ και προσθέτουμε μετάβαση από την κατάσταση q₁ στην κατάσταση q_f. Αυτή τη μετάβαση την ονομάζουμε b(a|b)^∗, επειδή από τον κόμβο q₁ φτάνουμε στην κατάσταση q₂ με λέξεις της μορφής b, μετά μπορούμε να κάνουμε βρόχο με a|b, οπότε παίρνουμε (a|b)^∗, και τέλος με μια ε-μετάβαση περνάμε στην q_f. Ισχύει μάλιστα b(a|b)^∗ϵ = b(a|b)^∗. Παίρνουμε το αυτόματο:

Μένει να απαλείψουμε την τελευταία κατάσταση, την q₁. Προσθέτουμε ακμή από την κατάσταση q_s στην κατάσταση q_f. Πώς θα την ονομάσουμε; Στην κατάσταση q₁ φτάνουμε μέσω ε-μετάβασης, την οποία μπορούμε απλά να παραλείψουμε. Μετά μπορούμε να κάνουμε βρόχο με a, οπότε παίρνουμε την κανονική έκφραση a^∗. Και τέλος, μέσω της ακμής φτάνουμε στην q_f, οπότε τη συνενώνουμε ακόμη με την b(a|b)^∗. Την ακμή λοιπόν την περιγράφουμε με την κανονική έκφραση a^∗ b(a|b)^∗.

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

Πηγές

• Το παράδειγμα και η περιγραφή του αλγορίθμου προέρχονται από το M. Sipser: Introduction to the Theory of Computation