Perangkaian bahasa nalar

Katakan kita mempunyai dua bahasa nalar L₁, L₂. Kita akan membuktikan bahawa perangkaian (konkatenasi) kedua-duanya, L = L₁ ∘ L₂, juga merupakan bahasa nalar.

Apakah perangkaian

Perangkaian dua rentetan “010” dan “1111” menghasilkan rentetan “0101111”. Perangkaian bahasa pula menghasilkan bahasa baharu yang dibina dengan merangkaikan setiap rentetan daripada satu bahasa dengan setiap rentetan daripada bahasa yang lain. Perangkaian dua rentetan dan dua bahasa ditandakan dengan bulatan kecil: ∘. Kita boleh mentakrifkan perangkaian bahasa L₁ dan L₂ seperti berikut:

$$L_1\circ L_2=\{a\circ b|a\in L_1,b\in L_2\}$$

Idea bukti

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

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

Kita membina automaton tak berketentuan A = ⟨Q, Σ, δ, q, F⟩ yang “mengandungi” kedua-dua automaton A₁ dan A₂. Idea asasnya ialah kita mula menerima rentetan dengan automaton A₁, dan apabila automaton A₁ sampai ke keadaan akhir, kita cuba menerima baki rentetan dengan automaton A₂. Jika automaton ini juga menerima bahagian rentetan itu, automaton A menerima rentetan tersebut.

Contoh

Katakan kita mempunyai automaton A₁ berikut, yang menerima rentetan tidak kosong yang terdiri daripada sifar sahaja, serta rentetan yang terdiri daripada satu digit satu diikuti oleh sifar sahaja (1, 10, 100, …):

Katakan juga kita mempunyai automaton A₂ berikut, yang menerima rentetan yang berakhir dengan 01:

Kita menyambungkan kedua-dua automaton dengan menambahkan peralihan epsilon dari semua keadaan akhir automaton A₁ ke keadaan awal automaton A₂, kemudian menjadikan keadaan akhir A₁ keadaan biasa. Keadaan awal bagi keseluruhan automaton baharu ialah keadaan awal automaton A₁:

Bagaimanakah automaton ini berfungsi? Kita mula menyimulasikan kerja automaton A₁. Jika kita beralih ke bekas keadaan akhir q₁ atau q₂, kita tahu bahawa automaton A₁ menerima sebahagian daripada rentetan itu. Supaya keseluruhan rentetan tergolong dalam bahasa L₁ ∘ L₂, baki rentetan itu mesti diterima pula oleh automaton kedua, A₂ — oleh itu, dari semua bekas keadaan akhir terdapat peralihan epsilon ke keadaan awal asal automaton A₂.

Sebagai contoh, ambil rentetan 0001. Rentetan ini tergolong dalam perangkaian kedua-dua bahasa kerana rentetan itu boleh terhasil daripada perangkaian rentetan 00 ∘ 01. Namun, rentetan itu juga boleh terhasil daripada perangkaian rentetan 0 ∘ 001. Dalam automaton kita, kedua-dua cara boleh disimulasikan. Automaton boleh mengikut laluan berikut:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

Melalui laluan ini, automaton mula-mula “menerima” bahagian rentetan 00, kemudian bahagian rentetan 01. Automaton juga boleh mengikut laluan berikut:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

dan dengan itu automaton mula-mula “menerima” bahagian rentetan 0, kemudian bahagian rentetan 001. Sudah tentu dalam kedua-dua kes kita sampai ke keadaan akhir p₂.

Kaedah formal

Sekali lagi: Kita mempunyai dua bahasa nalar L₁, L₂ dan dua automaton yang menerima bahasa ini:

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

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

• Q = Q₁ ∪ Q₂ (kita juga menganggap bahawa Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Fungsi peralihan δ dibina langkah demi langkah:

$$\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 \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{jika}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{jika}& q\in Q_2\end{array}$$

Sumber

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