Penukaran automaton kepada ungkapan nalar

Kita akan melihat cara menukarkan sebarang automaton terhingga kepada ungkapan nalar.

Penerangan algoritma

Input ialah suatu NFA A. Pertama sekali, kita menukarkannya kepada GNFA. Dalam fasa kedua, pada setiap langkah kita menghapuskan satu keadaan, membetulkan fungsi peralihan dengan sewajarnya, dan mengulanginya sehingga hanya tinggal dua keadaan — keadaan awal dan keadaan akhir. Di antara kedua-duanya terdapat satu anak panah yang berlabel ungkapan nalar, dan ungkapan inilah hasil keseluruhan algoritma. Jadi, keseluruhan kaedah ini terutamanya terdiri daripada penghapusan keadaan dan pembetulan automaton selepas itu supaya kita memperoleh automaton yang setara.

Penghapusan satu keadaan

Cara menghapuskan satu keadaan boleh digambarkan dengan contoh mudah. Andaikan sebahagian daripada automaton kita kelihatan seperti berikut:

dengan R_i ialah suatu ungkapan nalar. Bagaimanakah rupa automaton itu jika kita menghapuskan keadaan q_r? Bayangkan kita berada pada keadaan q_i dan bertanya: apakah semua rentetan yang boleh kita jana pada bahagian ini? Jika kita pergi dari keadaan q_i terus ke keadaan q_j, rentetan itu ialah semua rentetan yang sepadan dengan ungkapan nalar R₄.

Namun, jika kita pergi ke keadaan q_r, kita boleh menjana rentetan berbentuk R₁. Pada keadaan q_r kita boleh berulang bagi ungkapan nalar R₂, jadi sebenarnya kita boleh menjana rentetan berbentuk $R_1\circ (R_2^{\ast })$. Oleh sebab kita masih boleh pergi dari keadaan q_r ke keadaan q_j, kita menambahkan ungkapan nalar R₃. Secara keseluruhan, melalui laluan ini kita boleh memperoleh rentetan berbentuk $R_1\circ (R_2^{\ast })\circ R_3$.

Sekarang kita tahu bahawa bahagian automaton ini boleh menghasilkan rentetan berbentuk R₄ atau berbentuk $R_1\circ (R_2^{\ast })\circ R_3$. Hal ini sudah tentu boleh ditulis sebagai ungkapan nalar $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Kini kita boleh menghapuskan keadaan q_r dengan mudah, meninggalkan dua keadaan q_i dan q_j sahaja, dan menulis ungkapan nalar yang baru dikira menggantikan R₄:

Kaedah ini dilakukan bagi setiap anak panah dari setiap keadaan q_i ke suatu keadaan q_j, termasuk gelung, iaitu termasuk kes q_i = q_j.

Selepas menghapuskan satu keadaan, kita memperoleh automaton yang setara — automaton yang mengenal pasti bahasa yang sama.

Algoritma lengkap

Input ialah NFA A = ⟨Q, Σ, δ, q₀, F⟩.

1. Tukarkan NFA A kepada GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. Seterusnya huruf k menandakan bilangan keadaan dalam Z.
2. Jika k = 2, algoritma berakhir, dan ungkapan nalar yang terhasil berada pada anak panah antara keadaan awal dengan keadaan akhir.
3. Jika k>2, pilih sebarang keadaan q_r yang berbeza daripada keadaan awal dan keadaan akhir, iaitu q_r ≠ q₀′ dan q_r ≠ q_f′. Kemudian bina GNFA baharu Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ dengan $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ dan bagi semua q_i ∈ Q′′ ∖ {q_f′} dan semua q_j ∈ Q′′ ∖ {q₀′}, katakan $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ dengan R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Kemudian teruskan dengan langkah 2.

Contoh

Katakan input ialah automaton terhingga berikut:

Pertama sekali, kita menukarkannya kepada GNFA (peralihan ∅ yang tidak perlu tidak dilukis):

Sekarang kita menggunakan bahagian kedua algoritma dan menghapuskan satu nod. Kita mulakan dengan nod q₂. Kita menghapuskan nod q₂ dan menambahkan peralihan dari keadaan q₁ ke keadaan q_f. Peralihan ini dilabelkan b(a|b)^∗ kerana dari nod q₁ kita sampai ke keadaan q₂ bagi rentetan berbentuk b, kemudian kita boleh berulang bagi a|b, yang memberikan (a|b)^∗, dan akhirnya kita beralih ke q_f melalui peraturan epsilon. Di sini b(a|b)^∗ϵ = b(a|b)^∗. Kita memperoleh automaton:

Yang tinggal ialah menghapuskan keadaan terakhir, q₁. Kita menambahkan anak panah dari keadaan q_s ke keadaan q_f. Apakah labelnya? Kita sampai ke keadaan q₁ melalui peraturan epsilon, jadi bahagian ini boleh terus ditinggalkan. Kemudian kita boleh berulang bagi a, jadi kita memperoleh ungkapan nalar a^∗. Akhirnya kita sampai ke q_f melalui anak panah, jadi ungkapan itu dirangkaikan pula dengan b(a|b)^∗. Oleh itu, anak panah dilabelkan dengan ungkapan nalar a^∗ b(a|b)^∗.

Automaton kini hanya mempunyai dua keadaan, jadi algoritma berakhir. Ungkapan nalar yang terhasil berada pada anak panah itu.

Sumber

• Contoh dan penerangan algoritma diambil daripada M. Sipser: Introduction to the Theory of Computation