Ένωση κανονικών γλωσσών

Έστω δύο κανονικές γλώσσες L₁, L₂. Θα αποδείξουμε ότι η ένωσή τους L = L₁ ∪ L₂ είναι επίσης κανονική γλώσσα.

Μέθοδος με ντετερμινιστικό αυτόματο

Η ιδέα

Έχουμε δύο κανονικές γλώσσες L₁ και L₂ και θέλουμε να αποδείξουμε ότι η ένωσή τους L₁ ∪ L₂ είναι πάλι κανονική γλώσσα. Επειδή οι L₁ και L₂ είναι κανονικές γλώσσες, υπάρχουν πεπερασμένα αυτόματα A₁ και A₂ που αποδέχονται τις γλώσσες L₁ και L₂, δηλαδή ισχύει L(A₁) = L₁ και L(A₂) = L₂. Στη συνέχεια θα κατασκευάσουμε ένα πεπερασμένο αυτόματο A που θα αποδέχεται τη γλώσσα L₁ ∪ L₂, και έτσι θα αποδείξουμε ότι η γλώσσα L₁ ∪ L₂ είναι κανονική.

Πώς θα το κάνουμε; Έχουμε στη διάθεσή μας τα πεπερασμένα αυτόματα A₁ και A₂, που αποδέχονται τις επιμέρους γλώσσες. Μπορούμε να πούμε ότι η λέξη w ανήκει στη γλώσσα L₁ ∪ L₂ αν και μόνο αν την αποδέχεται τουλάχιστον ένα από τα αυτόματα A₁ ή A₂.

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

Μένει να διατυπώσουμε αυστηρά τι σημαίνει ότι το αυτόματο A «προσομοιώνει» τον υπολογισμό ενός άλλου αυτομάτου.

Αυστηρή διατύπωση

Έχουμε δύο κανονικές γλώσσες L₁ και L₂, που αποδέχονται τα πεπερασμένα αυτόματα

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2} ⟩ . \end{array}$

Θα κατασκευάσουμε ένα πεπερασμένο αυτόματο A = ⟨Q, Σ, δ, q, F⟩ που θα αποδέχεται τη γλώσσα L = L₁ ∪ L₂. Θα χρησιμοποιήσουμε την ιδέα της ταυτόχρονης προσομοίωσης δύο αυτομάτων A₁, A₂. Ας φανταστούμε ότι έχουμε στην είσοδο τη λέξη w = w₁w₂… w_n και ότι προσομοιώνουμε ταυτόχρονα την πορεία των αυτομάτων A₁ και A₂ για τη λέξη w. Η αρχική διαμόρφωση του αυτομάτου A₁ είναι ⟨q₁, w₁w₂… w_n⟩, ενώ η αρχική διαμόρφωση του A₂ είναι ⟨q₂, w₁w₂… w_n⟩. Σε κάθε αυτόματο εκτελούμε τώρα ένα βήμα υπολογισμού και καταλήγουμε στις διαμορφώσεις ⟨δ₁(q₁, w₁), w₂… w_n⟩ και ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Βλέπουμε ότι οι διαμορφώσεις αυτές διαφέρουν μόνο στο πρώτο στοιχείο· το δεύτερο – το μέρος της λέξης που δεν έχει διαβαστεί ακόμα – είναι πάντα το ίδιο. Άρα κατά την προσομοίωση δεν χρειάζεται να κρατάμε δύο διαμορφώσεις δύο αυτομάτων, αρκεί μία διαμόρφωση της μορφής ⟨⟨q_i, q_j⟩, w_l… w_n⟩, όπου q_i ∈ Q₁ και q_j ∈ Q₂. Με άλλα λόγια, το αυτόματο A που κατασκευάζουμε θα έχει αρχική διαμόρφωση ⟨⟨q₁, q₂⟩, w⟩. Το πρώτο μέρος του ζεύγους ⟨q₁, q₂⟩ είναι η κατάσταση στην οποία βρίσκεται τη στιγμή αυτή το αυτόματο A₁ και το δεύτερο μέρος είναι η τρέχουσα κατάσταση του αυτομάτου A₂.

Μπορούμε λοιπόν να γράψουμε ότι το αυτόματο A θα έχει σύνολο καταστάσεων Q = Q₁ × Q₂. Θα είναι το καρτεσιανό γινόμενο των καταστάσεων των δύο προηγούμενων αυτομάτων. Η ιδέα που ακολουθεί είναι ότι το αυτόματο A θα έχει αρχική κατάσταση ⟨q₁, q₂⟩ και, αν το αυτόματο A₁ μεταβαίνει για το σύμβολο w₁ στην κατάσταση q_i και το αυτόματο A₂ μεταβαίνει για το σύμβολο w₁ στην κατάσταση q_j, τότε το αυτόματο A μεταβαίνει για το σύμβολο w₁ στην κατάσταση ⟨q_i, q_j⟩.

Τη συνάρτηση μετάβασης δ τη γράφουμε ως εξής (εδώ υποθέτουμε ήδη ότι βρισκόμαστε στις καταστάσεις q_i και q_j):

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

Μένουν μόνο μικρές λεπτομέρειες. Για το αλφάβητο ισχύει Σ= Σ₁ ∪ Σ₂. Η αρχική κατάσταση είναι q = ⟨q₁, q₂⟩. Και οι τελικές καταστάσεις είναι όλα τα ζεύγη ⟨q_i, q_j⟩ για τα οποία ισχύει q_i ∈ F₁ ή q_j ∈ F₂.

Επεξήγηση με παράδειγμα

Έστω δύο αυτόματα. Το πρώτο είναι το αυτόματο A₁, που αποδέχεται όλες τις λέξεις (και την κενή λέξη) στις οποίες εναλλάσσονται μηδενικά και μονάδες, δηλαδή τις λέξεις της μορφής 01, 0101, 010101, …

Το δεύτερο αυτόματο A₂ αποδέχεται τις λέξεις που περιέχουν τουλάχιστον ένα μηδενικό:

Η ένωση αυτών των γλωσσών αποτελείται από τις λέξεις που είτε περιέχουν μηδενικό είτε έχουν τη μορφή 01, 0101, … Τώρα θα κατασκευάσουμε το πεπερασμένο αυτόματο A = ⟨Q, Σ, δ, q, F⟩ που θα αποδέχεται ακριβώς αυτή την ενωμένη γλώσσα. Πρώτα θα δούμε πώς θα είναι οι καταστάσεις του νέου αυτομάτου A. Θα είναι το καρτεσιανό γινόμενο των καταστάσεων του πρώτου και του δεύτερου αυτομάτου:

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

Έτσι προκύπτουν οι έξι καταστάσεις του αυτομάτου A, που αποδέχεται την ενωμένη γλώσσα L(A₁) ∪ L(A₂). Στο διάγραμμα θα έμοιαζαν ως εξής:

Μην ανησυχείς που έχουμε καταστάσεις που αποτελούνται από ζεύγη καταστάσεων – αυτό βοηθά απλώς να καταλαβαίνουμε καλύτερα τι συμβαίνει στο αυτόματο. Οι καταστάσεις θα μπορούσαν κάλλιστα να ονομάζονται απλά q₀, …, q₅. Τελικές είναι οι καταστάσεις που περιέχουν είτε την κατάσταση q₀ είτε την p₁, δηλαδή τις τελικές καταστάσεις των αρχικών αυτομάτων. Η αρχική κατάσταση είναι η ⟨q₀, p₀⟩.

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

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Και θα τον συμπληρώνουμε σταδιακά. Πρώτα βρίσκουμε πού οδηγεί η μετάβαση από την κατάσταση ⟨q₀, p₀⟩ με είσοδο 0. Βρίσκουμε πού οδηγεί η μετάβαση από την κατάσταση q₀ με είσοδο 0 στο αυτόματο A₁: οδηγεί στην κατάσταση q₁. Στο αυτόματο A₂ η μετάβαση από την p₀ με το μηδέν οδηγεί στην κατάσταση p₁. Γράφουμε λοιπόν στον πίνακα ⟨q₁, p₁⟩:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Με είσοδο 1 έχουμε: για το αυτόματο A₁ ισχύει δ₁(q₀, 1) = q₂ και για το αυτόματο A₂ ισχύει δ₂(p₀, 1) = p₀. Παίρνουμε έτσι την κατάσταση ⟨q₂, p₀⟩.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Συμπληρώνουμε τον υπόλοιπο πίνακα:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

Και με βάση αυτόν τον πίνακα σχεδιάζουμε το υπόλοιπο διάγραμμα.

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

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

Επειδή η κατάσταση ⟨q₂, p₁⟩ είναι τελική, το αυτόματο A αποδέχεται τη λέξη 0100. Τι θα γινόταν αν δίναμε τη λέξη 0100 στα αυτόματα A₁ και A₂; Το αυτόματο A₁ θα περνούσε διαδοχικά από τις καταστάσεις:

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

Το αυτόματο κατέληξε στην κατάσταση q₂, η οποία δεν είναι τελική, άρα το αυτόματο A₁ δεν θα αποδεχόταν αυτή τη λέξη. Και το αυτόματο A₂;

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

Η κατάσταση p₁ είναι τελική, άρα το αυτόματο A₂ θα αποδεχόταν τη λέξη 0100. Πρόσεξε ότι τα αυτόματα A₁ και A₂ κατέληξαν στις καταστάσεις q₂ και p₁, κάτι που συμφωνεί με το ότι το αυτόματο A κατέληξε στην κατάσταση ⟨q₂, p₁⟩.

Μέθοδος με μη ντετερμινιστικό αυτόματο

Παράδειγμα

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

Έχουμε λοιπόν δύο κανονικές γλώσσες L₁, L₂ και θέλουμε να αποδείξουμε ότι η ένωσή τους L = L₁ ∪ L₂ είναι επίσης κανονική γλώσσα. Επειδή οι L₁, L₂ είναι κανονικές γλώσσες, πρέπει να υπάρχουν αυτόματα A₁, A₂ που τις αποδέχονται. Δηλαδή ισχύει L(A₁) = L₁ και L(A₂) = L₂. Με τη βοήθεια αυτών των αυτομάτων κατασκευάζουμε ένα αυτόματο A που θα αποδέχεται τη γλώσσα L, δηλαδή L(A) = L.

Ας υποθέσουμε ότι τα πεπερασμένα αυτόματα A₁ και A₂ έχουν αυτή τη μορφή:

και

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

Αυστηρή διατύπωση

Έχουμε δύο αυτόματα A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ και A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Κατασκευάζουμε το αυτόματο A = ⟨Q, Σ, δ, q₀, F⟩, που θα αποδέχεται την ένωση των γλωσσών τις οποίες αποδέχονται τα προηγούμενα αυτόματα, δηλαδή L(A) = L(A₁) ∪ L(A₂). Ισχύουν τα εξής:

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

Και τη συνάρτηση μετάβασης δ ορίζουμε ως εξής:

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & αν & q \in Q_{1} \\ δ_{2} (q, a) & αν & q \in Q_{2} \\ {q_{1}, q_{2}} & αν & q = q_{0} \land a = ε \\ \emptyset & αν & q = q_{0} \land a \neq ε \end{cases}$

Πηγές

Κεφάλαια: Κλειστότητα κανονικών γλωσσών, Ένωση, Τομή, Διαφορά, Συμπλήρωμα, Παράθεση, Κλειστότητα Kleene

« Προηγούμενο: Κλειστότητα κανονικών γλωσσών

Επόμενο: Τομή »