Penutup bahasa reguler

Misalkan ada bahasa reguler L. Kita akan membuktikan bahwa penutup bahasa L juga merupakan bahasa reguler.

Apa itu penutup bahasa

Penutup bahasa L dilambangkan dengan L^∗. Penutup memuat semua string yang dapat disusun dengan konkatenasi sejumlah berhingga string dari bahasa L. Penutup dapat didefinisikan sebagai:

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

dengan ∘ menyatakan operasi konkatenasi. Penutup juga memuat string kosong, yaitu ϵ.

Prosedur formal

Prosedurnya sangat mirip dengan konkatenasi bahasa. Bedanya, alih-alih menyambung dua otomaton yang berbeda, kita menyambung satu otomaton dengan dirinya sendiri — dari state akhir otomaton kita buat transisi epsilon ke state awal otomaton. Namun, penutup juga harus memuat string kosong. Bagaimana caranya? State awal bisa saja kita jadikan state akhir. Otomaton seperti itu memang akan menerima string kosong, tetapi mungkin juga menerima string lain yang tidak seharusnya. Karena itu, sebagai gantinya kita buat state awal baru, dan dari state awal baru ini kita buat transisi epsilon ke state awal semula.

Ada bahasa reguler L₁ dan otomaton yang menerima bahasa tersebut:

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

Kita konstruksi otomaton nondeterministik A = ⟨Q, Σ, δ, q_s, F⟩ dengan:

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

Fungsi transisi δ didefinisikan sebagai 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

Misalkan ada otomaton A₁ berikut, yang menerima string 00 atau 11:

Jadi, penutup bahasa L(A₁) adalah bahasa semua string yang tersusun atas pasangan 00 dan 11, misalnya 0000, 110011, 11110000, dan seterusnya. Otomaton yang menerima penutup ini kita susun dengan membuat state awal baru q_s yang memiliki transisi epsilon ke bekas state awal q₀, lalu menambahkan transisi epsilon dari state q₃ dan q₄ ke state q₀:

Kita dapat memeriksa bahwa otomaton ini memang menerima string 0000, 110011, 11110000, tetapi tidak menerima, misalnya, string 1010.

Sumber

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