Κλειστότητα Kleene κανονικής γλώσσας

Έστω μια κανονική γλώσσα L. Θα αποδείξουμε ότι η κλειστότητα Kleene της γλώσσας L είναι πάλι κανονική γλώσσα.

Τι είναι η κλειστότητα μιας γλώσσας

Την κλειστότητα Kleene της γλώσσας L τη συμβολίζουμε L^∗. Περιέχει όλες τις λέξεις που μπορούν να προκύψουν από την παράθεση πεπερασμένου πλήθους λέξεων της γλώσσας L. Την κλειστότητα μπορούμε να την ορίσουμε ως:

$$L^{\ast }=\{a_1\circ a_2\circ \cdots \circ a_n|a_i\in L,n\in \mathbb{N}\},$$

όπου το ∘ δηλώνει την πράξη της παράθεσης. Η κλειστότητα περιέχει και την κενή λέξη, δηλαδή το ϵ.

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

Θα ακολουθήσουμε πολύ παρόμοια πορεία με την παράθεση γλωσσών. Μόνο που αντί να συνδέσουμε δύο διαφορετικά αυτόματα, θα συνδέσουμε ένα αυτόματο με τον εαυτό του – από τις τελικές καταστάσεις του αυτομάτου θα φέρουμε ε-μεταβάσεις προς την αρχική κατάσταση του αυτομάτου. Η κλειστότητα όμως πρέπει να περιέχει και την κενή λέξη. Πώς θα το πετύχουμε; Μπορούμε να κάνουμε την αρχική κατάσταση τελική. Τότε το αυτόματο θα αποδεχόταν την κενή λέξη, αλλά θα μπορούσε να αποδεχτεί και κάποια άλλη λέξη. Γι' αυτό δημιουργούμε μια νέα αρχική κατάσταση και από αυτήν τη νέα αρχική κατάσταση φέρνουμε μια ε-μετάβαση προς την αρχική κατάσταση του αρχικού αυτομάτου.

Έχουμε μια κανονική γλώσσα L₁ και ένα αυτόματο που την αποδέχεται:

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

Κατασκευάζουμε το μη ντετερμινιστικό αυτόματο A = ⟨Q, Σ, δ, q_s, F⟩, για το οποίο ισχύει:

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

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

$$\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 ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{αν}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{αν}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{αν}& q=q_s\wedge a\ne ϵ\end{array}$$

Παράδειγμα

Έστω το αυτόματο A₁, που αποδέχεται τις λέξεις 00 ή 11:

Η κλειστότητα Kleene της γλώσσας L(A₁) είναι λοιπόν η γλώσσα όλων των λέξεων που αποτελούνται από ζεύγη 00 και 11, για παράδειγμα 0000, 110011, 11110000 κτλ. Το αυτόματο που θα αποδεχόταν αυτή την κλειστότητα θα το κατασκευάζαμε δημιουργώντας μια νέα αρχική κατάσταση q_s με ε-μετάβαση προς την πρώην αρχική κατάσταση q₀ και προσθέτοντας ε-μεταβάσεις από τις καταστάσεις q₃ και q₄ προς την κατάσταση q₀:

Μπορούμε να επαληθεύσουμε ότι αυτό το αυτόματο πράγματι αποδέχεται τις λέξεις 0000, 110011, 11110000, αλλά δεν αποδέχεται, για παράδειγμα, τη λέξη 1010.

Πηγές

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