Gabungan bahasa reguler

Misalkan ada dua bahasa reguler L₁, L₂. Kita akan membuktikan bahwa gabungan keduanya, L = L₁ ∪ L₂, juga merupakan bahasa reguler.

Cara dengan otomaton deterministik

Ide pembuktian

Ada dua bahasa reguler L₁ dan L₂, dan kita ingin membuktikan bahwa gabungan keduanya, L₁ ∪ L₂, juga merupakan bahasa reguler. Karena L₁ dan L₂ adalah bahasa reguler, ada otomaton hingga A₁ dan A₂ yang menerima bahasa L₁ dan L₂, jadi berlaku L(A₁) = L₁ dan L(A₂) = L₂. Selanjutnya, kita susun otomaton hingga A yang menerima bahasa L₁ ∪ L₂. Dengan begitu, terbukti bahwa bahasa L₁ ∪ L₂ reguler.

Bagaimana caranya? Kita punya otomaton hingga A₁ dan A₂ yang menerima masing-masing bahasa. Dapat dikatakan bahwa string w termasuk bahasa L₁ ∪ L₂ jika dan hanya jika string tersebut diterima oleh setidaknya salah satu otomaton, A₁ atau A₂.

Otomaton A dapat bekerja sebagai berikut: untuk input w, otomaton menyimulasikan komputasi otomaton A₁ untuk input w. Jika A₁ menerima string w, A juga menerima string w. Jika A₁ menolak string w, A masih mencoba menyimulasikan komputasi A₂ untuk input w. Jika A₂ menerima string w, A juga menerima string w. Jika tidak, string tersebut ditolak.

Tinggal memformalkan apa artinya otomaton A “menyimulasikan” komputasi otomaton lain.

Formalisasi

Ada dua bahasa reguler L₁ dan L₂ yang diterima oleh otomaton hingga

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2} ⟩ . \end{array}$

Kita susun otomaton hingga A = ⟨Q, Σ, δ, q, F⟩ yang menerima bahasa L = L₁ ∪ L₂. Kita gunakan ide menyimulasikan dua otomaton A₁, A₂. Bayangkan inputnya adalah string w = w₁w₂… w_n, dan sekarang kita menyimulasikan jalannya otomaton A₁ dan A₂ untuk string w secara bersamaan. Konfigurasi awal otomaton A₁ adalah ⟨q₁, w₁w₂… w_n⟩, dan konfigurasi awal A₂ adalah ⟨q₂, w₁w₂… w_n⟩. Sekarang pada setiap otomaton kita lakukan satu langkah komputasi, sehingga kita sampai di konfigurasi ⟨δ₁(q₁, w₁), w₂… w_n⟩ dan ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Terlihat bahwa kedua konfigurasi ini hanya berbeda pada komponen pertama, sedangkan komponen kedua — bagian string yang belum dibaca — selalu sama. Karena itu, selama simulasi kita tidak perlu menyimpan dua konfigurasi untuk dua otomaton; cukup satu konfigurasi berbentuk ⟨⟨q_i, q_j⟩, w_l… w_n⟩, dengan q_i ∈ Q₁ dan q_j ∈ Q₂. Dengan kata lain, otomaton A yang sedang kita susun memiliki konfigurasi awal ⟨⟨q₁, q₂⟩, w⟩. Bagian pertama pasangan ⟨q₁, q₂⟩ menyatakan state tempat otomaton A₁ saat ini berada, dan komponen kedua menyatakan state otomaton A₂ saat ini.

Jadi, dapat kita tulis bahwa himpunan state otomaton A yang kita susun adalah Q = Q₁ × Q₂, yaitu hasil kali Kartesius dari state kedua otomaton sebelumnya. Ide berikutnya: otomaton A memiliki state awal ⟨q₁, q₂⟩, dan jika otomaton A₁ untuk simbol w₁ berpindah ke state q_i dan otomaton A₂ untuk simbol w₁ berpindah ke state q_j, otomaton A untuk simbol w₁ berpindah ke state ⟨q_i, q_j⟩.

Fungsi transisi δ kita tulis sebagai berikut (di sini kita asumsikan bahwa saat ini kita berada di state q_i dan q_j):

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

Tinggal beberapa hal kecil. Untuk alfabet berlaku Σ= Σ₁ ∪ Σ₂. State awalnya adalah q = ⟨q₁, q₂⟩. State akhirnya adalah semua pasangan ⟨q_i, q_j⟩ sedemikian sehingga q_i ∈ F₁ atau q_j ∈ F₂.

Ilustrasi prosedur

Misalkan ada dua otomaton. Yang pertama adalah otomaton A₁, yang menerima semua string (termasuk string kosong) dengan angka nol dan satu yang berselang-seling, yaitu string berbentuk 01, 0101, 010101, …

Otomaton kedua, A₂, menerima string yang memuat setidaknya satu angka nol:

Gabungan kedua bahasa ini adalah string yang memuat nol atau berbentuk 01, 0101, … Sekarang kita susun otomaton hingga A = ⟨Q, Σ, δ, q, F⟩ yang menerima bahasa gabungan ini. Pertama, kita lihat seperti apa state otomaton baru A. State-statenya adalah hasil kali Kartesius dari state otomaton pertama dan kedua:

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

Inilah keenam state otomaton A yang menerima bahasa gabungan L(A₁) ∪ L(A₂). Dalam diagram, state-state tersebut terlihat seperti ini:

Jangan kaget bahwa ada state yang terdiri atas pasangan state — penamaan ini hanya membantu kita memahami apa yang sebenarnya terjadi di dalam otomaton. State-state tersebut boleh saja diberi nama biasa q₀, …, q₅. State akhir adalah state yang memuat state q₀ atau p₁, yaitu state akhir otomaton semula. State awalnya adalah ⟨q₀, p₀⟩.

Sekarang kita harus mencari semua transisi. Kita buat tabel seperti ini:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Tabel ini kita lengkapi sedikit demi sedikit. Pertama, kita cari ke mana transisi dari state ⟨q₀, p₀⟩ untuk input 0. Kita cari ke mana transisi dari state q₀ untuk input 0 pada otomaton A₁: transisinya menuju state q₁. Pada otomaton A₂, transisi dari p₀ untuk nol menuju state p₁. Jadi, ke dalam tabel kita tuliskan ⟨q₁, p₁⟩:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Untuk input 1 diperoleh: pada otomaton A₁ berlaku δ₁(q₀, 1) = q₂, dan pada otomaton A₂ berlaku δ₂(p₀, 1) = p₀. Jadi, kita memperoleh state ⟨q₂, p₀⟩.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Kita lengkapi sisa tabelnya:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

Berdasarkan tabel ini, kita tinggal melengkapi sisa diagramnya.

Kita dapat mencoba apakah otomaton bekerja sebagaimana mestinya. Kita coba menerima string 0100. Otomaton secara berurutan melewati state-state

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

Karena state ⟨q₂, p₁⟩ adalah state akhir, otomaton A menerima string 0100. Bagaimana hasilnya jika kita mencoba menerima string 0100 dengan otomaton A₁ dan A₂? Otomaton A₁ secara berurutan melewati state-state berikut:

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

Otomaton berhenti di state q₂, yang bukan state akhir, sehingga otomaton A₁ tidak menerima string ini. Bagaimana dengan otomaton A₂?

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

State p₁ adalah state akhir, sehingga otomaton A₂ menerima string 0100. Perhatikan bahwa otomaton A₁ dan A₂ berhenti di state q₂ dan p₁, sesuai dengan otomaton A yang berhenti di state ⟨q₂, p₁⟩.

Cara dengan otomaton nondeterministik

Contoh

Ketertutupan himpunan bahasa reguler terhadap gabungan juga dapat dibuktikan dengan mengonstruksi otomaton nondeterministik, yang jauh lebih sederhana.

Jadi, ada dua bahasa reguler L₁, L₂, dan kita ingin membuktikan bahwa gabungan keduanya, L = L₁ ∪ L₂, juga merupakan bahasa reguler. Karena L₁, L₂ adalah bahasa reguler, pasti ada otomaton A₁, A₂ yang menerima bahasa-bahasa tersebut. Artinya, berlaku L(A₁) = L₁ dan L(A₂) = L₂. Dengan otomaton-otomaton ini, kita konstruksi otomaton A yang menerima bahasa L, yaitu L(A) = L.

Misalkan otomaton hingga A₁ dan A₂ terlihat seperti ini:

dan

Otomaton yang menerima gabungan kedua bahasa dapat dikonstruksi dengan membuat state awal baru dan membuat dua transisi epsilon dari state ini ke state awal semula. Selesai. Otomatonnya terlihat seperti ini:

Formalisasi

Ada dua otomaton A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ dan A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Kita konstruksi otomaton A = ⟨Q, Σ, δ, q₀, F⟩ yang menerima gabungan bahasa-bahasa yang diterima kedua otomaton tersebut, yaitu L(A) = L(A₁) ∪ L(A₂). Di sini berlaku:

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

Fungsi transisi δ didefinisikan sebagai berikut:

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & jika & q \in Q_{1} \\ δ_{2} (q, a) & jika & q \in Q_{2} \\ {q_{1}, q_{2}} & jika & q = q_{0} \land a = ε \\ \emptyset & jika & q = q_{0} \land a \neq ε \end{cases}$

Sumber

Daftar isi: Sifat ketertutupan bahasa reguler, Gabungan bahasa reguler, Irisan bahasa reguler, Selisih bahasa reguler, Komplemen bahasa reguler, Konkatenasi bahasa reguler, Penutup bahasa reguler

« Artikel sebelumnya: Sifat ketertutupan bahasa reguler

Artikel berikutnya: Irisan bahasa reguler »