Kesatuan bahasa nalar

Katakan kita mempunyai dua bahasa nalar L₁, L₂. Kita akan membuktikan bahawa kesatuan kedua-duanya, L = L₁ ∪ L₂, juga merupakan bahasa nalar.

Kaedah menggunakan automaton berketentuan

Idea kaedah

Kita mempunyai dua bahasa nalar L₁ dan L₂ dan mahu membuktikan bahawa kesatuannya, L₁ ∪ L₂, juga bahasa nalar. Oleh sebab L₁ dan L₂ ialah bahasa nalar, wujud automaton terhingga A₁ dan A₂ yang menerima bahasa L₁ dan L₂, iaitu L(A₁) = L₁ dan L(A₂) = L₂. Kita akan membina automaton terhingga A yang menerima bahasa L₁ ∪ L₂, dan dengan itu membuktikan bahawa bahasa L₁ ∪ L₂ ialah bahasa nalar.

Bagaimanakah caranya? Kita mempunyai automaton terhingga A₁ dan A₂ yang menerima setiap bahasa itu. Kita boleh mengatakan bahawa rentetan w tergolong dalam bahasa L₁ ∪ L₂ jika dan hanya jika rentetan itu diterima oleh sekurang-kurangnya satu daripada automaton A₁ atau A₂.

Automaton A boleh berfungsi begini: bagi input w, automaton itu menyimulasikan pengiraan automaton A₁ bagi input w. Jika A₁ menerima rentetan w, A juga menerima rentetan w. Jika A₁ menolak rentetan w, A cuba pula menyimulasikan pengiraan A₂ bagi input w. Jika A₂ menerima rentetan w, A juga menerima rentetan w. Jika tidak, rentetan itu ditolak.

Yang tinggal ialah memformalkan maksud automaton A “menyimulasikan” pengiraan automaton lain.

Formalisasi

Kita mempunyai dua bahasa nalar L₁ dan L₂ yang diterima oleh automaton terhingga

$\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 membina automaton terhingga A = ⟨Q, Σ, δ, q, F⟩ yang menerima bahasa L = L₁ ∪ L₂. Kita menggunakan idea menyimulasikan dua automaton A₁, A₂. Bayangkan input ialah rentetan w = w₁w₂… w_n, dan kita menyimulasikan perjalanan automaton A₁ dan A₂ bagi rentetan w secara serentak. Konfigurasi awal automaton A₁ ialah ⟨q₁, w₁w₂… w_n⟩, dan konfigurasi awal A₂ ialah ⟨q₂, w₁w₂… w_n⟩. Sekarang kita melakukan satu langkah pengiraan dalam setiap automaton dan sampai ke konfigurasi ⟨δ₁(q₁, w₁), w₂… w_n⟩ dan ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Kita lihat bahawa konfigurasi ini hanya berbeza pada komponen pertama; komponen kedua — bahagian rentetan yang belum dibaca — sentiasa sama. Oleh itu, semasa simulasi kita tidak perlu menyimpan dua konfigurasi bagi dua automaton; cukup satu konfigurasi berbentuk ⟨⟨q_i, q_j⟩, w_l… w_n⟩, dengan q_i ∈ Q₁ dan q_j ∈ Q₂. Dengan kata lain, automaton A yang kita bina mempunyai konfigurasi awal ⟨⟨q₁, q₂⟩, w⟩. Komponen pertama pasangan ⟨q₁, q₂⟩ mewakili keadaan semasa automaton A₁, dan komponen kedua mewakili keadaan semasa automaton A₂.

Oleh itu, kita boleh menulis bahawa set keadaan automaton A ialah Q = Q₁ × Q₂, iaitu hasil darab Cartes bagi keadaan dua automaton tadi. Idea seterusnya ialah: automaton A mempunyai keadaan awal ⟨q₁, q₂⟩, dan jika automaton A₁ beralih ke keadaan q_i bagi simbol w₁ manakala automaton A₂ beralih ke keadaan q_j bagi simbol w₁, automaton A beralih ke keadaan ⟨q_i, q_j⟩ bagi simbol w₁.

Fungsi peralihan δ ditulis seperti berikut (di sini kita menganggap bahawa kita sedang berada pada keadaan q_i dan q_j):

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

Yang tinggal hanyalah perkara kecil. Abjadnya ialah Σ= Σ₁ ∪ Σ₂. Keadaan awalnya ialah q = ⟨q₁, q₂⟩. Keadaan akhir pula ialah semua pasangan ⟨q_i, q_j⟩ yang memenuhi syarat q_i ∈ F₁ atau q_j ∈ F₂.

Ilustrasi kaedah

Katakan kita mempunyai dua automaton. Yang pertama ialah automaton A₁ yang menerima semua rentetan (termasuk rentetan kosong) yang sifar dan satunya berselang-seli, iaitu rentetan berbentuk 01, 0101, 010101, …

Automaton kedua, A₂, menerima rentetan yang mengandungi sekurang-kurangnya satu sifar:

Kesatuan kedua-dua bahasa ini ialah rentetan yang sama ada mengandungi sifar atau berbentuk 01, 0101, … Sekarang kita membina automaton terhingga A = ⟨Q, Σ, δ, q, F⟩ yang menerima bahasa kesatuan ini. Pertama sekali, kita lihat rupa keadaan automaton baharu A. Keadaannya ialah hasil darab Cartes bagi keadaan automaton 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 enam keadaan automaton A yang menerima bahasa kesatuan L(A₁) ∪ L(A₂). Dalam gambar rajah, keadaan itu kelihatan seperti berikut:

Jangan terkejut kerana terdapat keadaan yang terdiri daripada pasangan keadaan — pasangan ini hanya membantu kita memahami apa yang sebenarnya berlaku dalam automaton. Keadaan itu boleh sahaja dinamakan seperti biasa, q₀, …, q₅. Keadaan akhir ialah keadaan yang mengandungi sama ada keadaan q₀ atau p₁, iaitu keadaan akhir bagi automaton asal. Keadaan awal ialah ⟨q₀, p₀⟩.

Sekarang kita perlu mencari semua peralihan. Kita tulis jadual seperti berikut:

$\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}$

Kemudian kita lengkapkan jadual itu langkah demi langkah. Pertama, kita tentukan ke mana peralihan dari keadaan ⟨q₀, p₀⟩ menuju bagi input 0. Kita cari ke mana peralihan dari keadaan q₀ bagi input 0 menuju dalam automaton A₁: peralihan itu menuju ke keadaan q₁. Dalam automaton A₂, peralihan dari p₀ bagi sifar menuju ke keadaan p₁. Jadi, kita tulis ⟨q₁, p₁⟩ dalam jadual:

$\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}$

Bagi input 1 kita peroleh: bagi automaton A₁, δ₁(q₀, 1) = q₂, dan bagi automaton A₂, δ₂(p₀, 1) = p₀. Jadi, kita memperoleh keadaan ⟨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 lengkapkan baki jadual:

$\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 jadual ini, kita hanya perlu melengkapkan baki gambar rajah.

Kita boleh menyemak bahawa automaton ini berfungsi dengan betul. Mari kita cuba menerima rentetan 0100. Automaton melalui keadaan berikut satu demi satu:

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

Oleh sebab keadaan ⟨q₂, p₁⟩ ialah keadaan akhir, automaton A menerima rentetan 0100. Apakah yang berlaku jika kita cuba menerima rentetan 0100 dengan automaton A₁ dan A₂? Automaton A₁ melalui keadaan berikut satu demi satu:

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

Automaton itu berakhir pada keadaan q₂, yang bukan keadaan akhir, jadi automaton A₁ tidak menerima rentetan ini. Bagaimana pula dengan automaton A₂?

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

Keadaan p₁ ialah keadaan akhir, jadi automaton A₂ menerima rentetan 0100. Perhatikan bahawa automaton A₁ dan A₂ berakhir pada keadaan q₂ dan p₁, dan hal ini sepadan dengan automaton A yang berakhir pada keadaan ⟨q₂, p₁⟩.

Kaedah menggunakan automaton tak berketentuan

Contoh

Ketertutupan set bahasa nalar terhadap kesatuan juga boleh dibuktikan dengan membina automaton tak berketentuan, dan cara ini jauh lebih mudah.

Kita mempunyai dua bahasa nalar L₁, L₂ dan mahu membuktikan bahawa kesatuannya, L = L₁ ∪ L₂, juga bahasa nalar. Oleh sebab L₁, L₂ ialah bahasa nalar, mesti wujud automaton A₁, A₂ yang menerima bahasa ini, iaitu L(A₁) = L₁ dan L(A₂) = L₂. Dengan menggunakan automaton ini, kita membina automaton A yang menerima bahasa L, iaitu L(A) = L.

Andaikan automaton terhingga A₁ dan A₂ kelihatan seperti berikut:

dan

Automaton yang menerima kesatuan kedua-dua bahasa dibina dengan menambahkan keadaan awal baharu dan melukis dua peralihan epsilon dari keadaan ini ke keadaan awal asal. Itu sahaja. Automaton itu kelihatan seperti berikut:

Formalisasi

Kita mempunyai dua automaton A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ dan A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Kita membina automaton A = ⟨Q, Σ, δ, q₀, F⟩ yang menerima kesatuan bahasa yang diterima oleh dua automaton tadi, iaitu L(A) = L(A₁) ∪ L(A₂). Dalam automaton ini:

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

Fungsi peralihan δ ditakrifkan seperti 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

Kandungan: Sifat ketertutupan bahasa nalar, Kesatuan bahasa nalar, Persilangan bahasa nalar, Beza bahasa nalar, Pelengkap bahasa nalar, Perangkaian bahasa nalar, Tutupan bahasa nalar

« Artikel sebelumnya: Sifat tertutup bahasa nalar

Artikel seterusnya: Persilangan bahasa nalar »