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

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

Παράδειγμα

Πριν περιγράψουμε τον ίδιο τον αλγόριθμο, θα δούμε σε ένα παράδειγμα τι ακριβώς θέλουμε να πετύχουμε. Έστω αυτή η κανονική έκφραση: a(b|c)x^∗. Με λόγια, τη γλώσσα που παράγει η κανονική έκφραση θα την περιγράφαμε ως τις λέξεις που αρχίζουν με το γράμμα «a», μετά ακολουθεί είτε το γράμμα «b» είτε το «c» και στη συνέχεια οποιοδήποτε πλήθος γραμμάτων «x». Θα μπορούσαμε να κατασκευάσουμε αυτόματο που θα αποδεχόταν αυτή τη γλώσσα; Βεβαίως, κοίτα:

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

Περιγραφή του αλγορίθμου μετατροπής κανονικής έκφρασης σε αυτόματο

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

1. R = a για κάποιο σύμβολο a ∈ Σ. Δηλαδή η κανονική έκφραση είναι ένα μόνο σύμβολο του αλφαβήτου Σ πάνω στο οποίο δουλεύουμε. Το αυτόματο που θα αποδεχόταν ένα σύμβολο a θα έμοιαζε ως εξής:

   

2. R = ϵ, η κενή λέξη. Το αυτόματο που θα αποδεχόταν την κενή λέξη θα έμοιαζε ως εξής:

   

3. R = ∅, κανονική έκφραση που παράγει την κενή γλώσσα. Το αυτόματο που θα αναγνώριζε μια τέτοια γλώσσα είναι το εξής:

   

4. R = R₁ ∪ R₂, όπου R₁, R₂ είναι κανονικές εκφράσεις. Ήδη ξέρουμε ότι η ένωση κανονικών γλωσσών είναι πάλι κανονική γλώσσα και ότι μπορούμε να κατασκευάσουμε αυτόματο που αποδέχεται μια τέτοια γλώσσα. Με άλλα λόγια, υποθέτουμε ότι έχουμε αυτόματα που αναγνωρίζουν τη γλώσσα που παράγουν οι εκφράσεις R₁ και R₂ και με τη βοήθειά τους κατασκευάζουμε αυτόματο που αποδέχεται τη γλώσσα που παράγει η έκφραση R₁ ∪ R₂. Παράδειγμα: αν R₁ = a και R₂ = ϵ, τότε σύμφωνα με τη μέθοδο παίρνουμε αυτό το αυτόματο:

   

5. R = R₁ ∘ R₂, όπου R₁, R₂ είναι κανονικές εκφράσεις. Η ίδια περίπτωση όπως στο προηγούμενο σημείο. Η παράθεση κανονικών γλωσσών είναι κανονική γλώσσα και μπορούμε έτσι να κατασκευάσουμε αυτόματο που θα αποδέχεται μια τέτοια γλώσσα. Αν λοιπόν R₁ = a, R₂ = b, η παράθεση θα έμοιαζε ως εξής:

   

6. $R=(R_1^{\ast })$, όπου R₁ είναι κανονική έκφραση. Πάλι ξέρουμε ότι η κλειστότητα Kleene κανονικής γλώσσας είναι κανονική γλώσσα. Άρα αν R = a^∗, το αυτόματο θα έμοιαζε ως εξής:

   

Εφαρμόζοντας διαδοχικά αυτά τα σημεία μετατρέπουμε ολόκληρη την κανονική έκφραση σε πεπερασμένο αυτόματο.

Πλήρες παράδειγμα

Θα δοκιμάσουμε να μετατρέψουμε την κανονική έκφραση (a|bc)^∗. Σταδιακά παίρνουμε αυτά τα αυτόματα:

Αυτό το τελικό αυτόματο αποδέχεται τη γλώσσα που παράγει η κανονική έκφραση (a|bc)^∗. Φυσικά το αυτόματο είναι τρομερά περίπλοκο και σίγουρα υπάρχει πολύ απλούστερο αυτόματο που αποδέχεται την ίδια γλώσσα. Μπορούμε να χρησιμοποιήσουμε τον αλγόριθμο μετατροπής NFA σε DFA και στη συνέχεια να κάνουμε ελαχιστοποίηση του αυτομάτου.

Πηγές

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