Τομή κανονικών γλωσσών

Έστω δύο κανονικές γλώσσες 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₂ είναι κανονική.

Μια λέξη ανήκει στην τομή των γλωσσών αν ανήκει στη γλώσσα L₁ και ταυτόχρονα στη γλώσσα L₂. Άρα τη λέξη πρέπει να την αποδέχεται το αυτόματο A₁ και ταυτόχρονα το αυτόματο A₂. Θα χρησιμοποιήσουμε ακριβώς την ίδια ιδέα που χρησιμοποιήσαμε στην ένωση κανονικών γλωσσών, αλλάζοντας μόνο το σύνολο των τελικών καταστάσεων.

Αυστηρή διατύπωση της μεθόδου

Έχουμε δύο αυτόματα,

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Κατασκευάζουμε το αυτόματο A = ⟨Q, Σ, δ, q, F⟩ που αποδέχεται τη γλώσσα L(A₁) ∩ L(A₂). Ισχύει ότι

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

Για τη συνάρτηση μετάβασης δ θα ισχύει η ακόλουθη σχέση:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

Παράδειγμα

Έστω το αυτόματο A₁, που αποδέχεται όλες τις λέξεις που περιέχουν άρτιο πλήθος μονάδων:

και το αυτόματο A₂, που αποδέχεται τις λέξεις που περιέχουν περιττό πλήθος μηδενικών:

Θα κατασκευάσουμε το αυτόματο που θα αποδέχεται την τομή αυτών των γλωσσών. Το σύνολο καταστάσεων του αυτομάτου έχει τη μορφή Q = Q₁ × Q₂, η αρχική κατάσταση είναι η ⟨q₀, p₀⟩ και οι τελικές καταστάσεις είναι τα στοιχεία του F₁ × F₂:

Στη συνέχεια συμπληρώνουμε τις μεταβάσεις με τον τύπο δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

Σε αυτό το αυτόματο, για παράδειγμα, από την κατάσταση ⟨q₀, p₀⟩ υπάρχει μετάβαση για το σύμβολο 0 στην κατάσταση ⟨q₀,p₁⟩. Αυτό σημαίνει ότι το αυτόματο A₁ έχει από την κατάσταση q₀ μετάβαση για το σύμβολο 0 πίσω στην κατάσταση q₀. Το αυτόματο A₂ έχει για το σύμβολο 0 μετάβαση από την κατάσταση p₀ στην κατάσταση p₁.

Μπορούμε να δοκιμάσουμε το αυτόματο. Θα πρέπει να αποδέχεται λέξεις όπως η 110 ή η 00000 (περιέχουν άρτιο πλήθος μονάδων και ταυτόχρονα περιττό πλήθος μηδενικών), αλλά δεν θα πρέπει να αποδέχεται λέξεις όπως οι 11, 111, 1010.

Πηγές

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