Παράθεση κανονικών γλωσσών

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

Τι είναι η συνένωση

Αν παραθέσουμε τις λέξεις «010» και «1111», προκύπτει η λέξη «0101111». Με την παράθεση γλωσσών προκύπτει μια νέα γλώσσα, που τη φτιάχνουμε παραθέτοντας κάθε λέξη της μιας γλώσσας με κάθε λέξη της άλλης. Την παράθεση δύο λέξεων και δύο γλωσσών θα τη συμβολίζουμε με ένα κυκλάκι: ∘. Τότε μπορούμε να ορίσουμε την παράθεση των γλωσσών L₁ και L₂ ως εξής:

$$L_1\circ L_2=\{a\circ b|a\in L_1,b\in L_2\}$$

Η ιδέα της απόδειξης

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

$$\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⟩ που θα «περιέχει μέσα του» και τα δύο αυτόματα A₁ και A₂. Η βασική ιδέα είναι ότι αρχίζουμε να διαβάζουμε τη λέξη με το αυτόματο A₁ και, όταν το αυτόματο A₁ φτάσει σε τελική κατάσταση, δοκιμάζουμε αν το υπόλοιπο της λέξης το αποδέχεται το αυτόματο A₂. Αν και αυτό το αυτόματο αποδέχεται το υπόλοιπο της λέξης, τότε το αυτόματο A αποδέχεται τη λέξη.

Παράδειγμα

Έστω το αυτόματο A₁, που αποδέχεται τις μη κενές λέξεις που αποτελούνται μόνο από μηδενικά και τις λέξεις που αποτελούνται από μια μονάδα, μετά την οποία ακολουθούν μόνο μηδενικά (1, 10, 100, …):

και το αυτόματο A₂, που αποδέχεται τις λέξεις που τελειώνουν σε 01:

Συνδέουμε τα αυτόματα προσθέτοντας από όλες τις τελικές καταστάσεις του A₁ ε-μεταβάσεις προς την αρχική κατάσταση του A₂ και στη συνέχεια κάνουμε τις τελικές καταστάσεις του A₁ απλές καταστάσεις. Η αρχική κατάσταση ολόκληρου του νέου αυτομάτου θα είναι η αρχική κατάσταση του A₁:

Πώς θα λειτουργεί το αυτόματο; Αρχίζουμε να προσομοιώνουμε τη λειτουργία του αυτομάτου A₁. Αν περάσουμε σε μια πρώην τελική κατάσταση q₁ ή q₂, ξέρουμε ότι το αυτόματο A₁ αποδέχεται ένα μέρος αυτής της λέξης. Για να ανήκει ολόκληρη η λέξη στη γλώσσα L₁ ∘ L₂, το υπόλοιπο της λέξης πρέπει να το αποδεχτεί το δεύτερο αυτόματο A₂ – γι' αυτό από όλες τις πρώην τελικές καταστάσεις οδηγούν ε-μεταβάσεις στην αρχική κατάσταση του αυτομάτου A₂.

Ας πάρουμε για παράδειγμα τη λέξη 0001. Ανήκει στην παράθεση των δύο γλωσσών, επειδή η λέξη μπορεί να προκύψει από την παράθεση των λέξεων 00 ∘ 01. Μπορεί όμως εξίσου να προκύψει από την παράθεση των λέξεων 0 ∘ 001. Στο αυτόματό μας μπορούμε να προσομοιώσουμε και τους δύο τρόπους. Το αυτόματο μπορεί να ακολουθήσει αυτή τη διαδρομή:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

Σε αυτή τη διαδρομή το αυτόματο θα «αποδεχόταν» πρώτα το μέρος 00 της λέξης και μετά το μέρος 01. Ή μπορεί να ακολουθήσει αυτή τη διαδρομή:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

και το αυτόματο θα «αποδεχόταν» πρώτα το μέρος 0 της λέξης και μετά το μέρος 001. Και στις δύο περιπτώσεις φυσικά καταλήγουμε στην τελική κατάσταση p₂.

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

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

$$\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⟩, για το οποίο ισχύει:

• Q = Q₁ ∪ Q₂ (υποθέτουμε επίσης ότι Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Τη συνάρτηση μετάβασης δ τη φτιάχνουμε σταδιακά:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{αν}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{αν}& q\in F_1\wedge a\ne \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{αν}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{αν}& q\in Q_2\end{array}$$

Πηγές

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