Γενικευμένο μη ντετερμινιστικό πεπερασμένο αυτόματο

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

Ορισμός

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

Βλέπουμε ότι π.χ. από την κατάσταση q₂ οδηγεί μετάβαση στην κατάσταση q_f που φέρει την κανονική έκφραση a^∗ b. Οι υπόλοιπες απαιτήσεις για το GNFA:

• Η αρχική κατάσταση q₀ πρέπει να έχει μετάβαση προς όλες τις άλλες καταστάσεις. Στο σχήμα βλέπουμε ότι από την κατάσταση q₀ οδηγούν μεταβάσεις σε όλες τις υπόλοιπες καταστάσεις.
• Στο GNFA υπάρχει μόνο μία τελική κατάσταση και όλες οι άλλες καταστάσεις έχουν μετάβαση προς αυτήν. Όπως φαίνεται στο σχήμα, όλες οι καταστάσεις έχουν βέλος που δείχνει στην q_f.
• Η αρχική κατάσταση δεν επιτρέπεται να συμπίπτει με την τελική. Το GNFA έχει επομένως τουλάχιστον δύο καταστάσεις.
• Όλες οι άλλες καταστάσεις, εκτός από την αρχική και την τελική, πρέπει να έχουν μεταβάσεις προς όλες τις άλλες καταστάσεις, εκτός από την αρχική και την τελική. Συμπεριλαμβανομένων των βρόχων (μετάβαση από την κατάσταση q_i στην κατάσταση q_i).

Μετατροπή συνήθους NFA σε GNFA

Αν έχουμε ένα NFA, η μετατροπή σε GNFA είναι απλή.

1. Δημιουργούμε μια νέα αρχική κατάσταση q_s και μια ε-μετάβαση προς την παλιά αρχική κατάσταση.
2. Δημιουργούμε μια νέα τελική κατάσταση q_f και από όλες τις παλιές τελικές καταστάσεις φέρνουμε ε-μεταβάσεις προς την κατάσταση q_f. Τις παλιές τελικές καταστάσεις τις κάνουμε απλές καταστάσεις.
3. Αν κάπου υπάρχει πολλαπλή μετάβαση (δηλαδή αν από την κατάσταση q₁ φτάνουμε στην κατάσταση q₂ και με το σύμβολο 0 και με το σύμβολο 1), τότε συγχωνεύουμε αυτούς τους κανόνες σε μία κανονική έκφραση και όλα τα αρχικά σύμβολα τα συνδέουμε με τον τελεστή της ένωσης (δηλαδή επιγράφουμε το βέλος με την κανονική έκφραση 0|1).
4. Αν στο αυτόματο λείπει κάποια μετάβαση που σύμφωνα με τον ορισμό θα έπρεπε να υπάρχει, τη δημιουργούμε και την επιγράφουμε με την κανονική έκφραση ∅. Έτσι δεν αλλάζουμε τη γλώσσα που αποδέχεται το αυτόματο, επειδή μια τέτοια μετάβαση δεν εκτελείται ποτέ.

Αυτό το αυτόματο μπορούμε να το χρησιμοποιήσουμε για τη μετατροπή του αυτομάτου σε κανονική έκφραση.