Tutupan bahasa nalar

Kita mempunyai bahasa nalar L. Kita akan membuktikan bahawa tutupan bahasa L juga merupakan bahasa nalar.

Apakah tutupan bahasa

Tutupan bahasa L ditandakan dengan L^∗. Tutupan ini mengandungi semua rentetan yang boleh dibentuk dengan merangkaikan sebilangan terhingga rentetan daripada bahasa L. Tutupan boleh ditakrifkan sebagai:

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

dengan ∘ ialah operasi perangkaian. Tutupan juga mengandungi rentetan kosong, iaitu ϵ.

Kaedah formal

Kaedahnya sangat serupa dengan perangkaian bahasa. Bezanya, kita tidak menyambungkan dua automaton yang berlainan, tetapi menyambungkan satu automaton dengan dirinya sendiri — dari keadaan akhir automaton kita melukis peralihan epsilon ke keadaan awal automaton itu. Namun, tutupan juga mesti mengandungi rentetan kosong. Bagaimanakah caranya? Kita boleh menjadikan keadaan awal sebagai keadaan akhir. Automaton itu akan menerima rentetan kosong, tetapi mungkin juga menerima rentetan lain yang tidak sepatutnya. Oleh itu, sebaliknya kita membina keadaan awal baharu dan melukis peralihan epsilon dari keadaan awal baharu ini ke keadaan awal asal.

Kita mempunyai bahasa nalar L₁ dan automaton yang menerima bahasa ini:

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

Kita membina automaton tak berketentuan A = ⟨Q, Σ, δ, q_s, F⟩ dengan

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

Fungsi peralihan δ ditakrifkan seperti berikut:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{jika}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{jika}& q\in F_1\wedge a\ne ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{jika}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{jika}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{jika}& q=q_s\wedge a\ne ϵ\end{array}$$

Contoh

Katakan kita mempunyai automaton A₁ berikut, yang menerima rentetan 00 atau 11:

Tutupan bahasa L(A₁) ialah bahasa semua rentetan yang terdiri daripada pasangan 00 dan 11, contohnya 0000, 110011, 11110000 dan sebagainya. Automaton yang menerima tutupan ini dibina dengan menambahkan keadaan awal baharu q_s dengan peralihan epsilon ke bekas keadaan awal q₀, serta menambahkan peralihan epsilon dari keadaan q₃ dan q₄ ke keadaan q₀:

Kita boleh menyemak bahawa automaton ini benar-benar menerima rentetan 0000, 110011, 11110000, tetapi tidak menerima, misalnya, rentetan 1010.

Sumber

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