Konversi otomaton menjadi ekspresi reguler

Kita akan melihat cara mengonversi sembarang otomaton hingga menjadi ekspresi reguler.

Penjelasan algoritma

Inputnya adalah suatu NFA A. Pertama, NFA ini kita ubah menjadi GNFA. Pada tahap kedua, di setiap langkah kita menghapus satu state, menyesuaikan fungsi transisi dengan benar, lalu mengulanginya sampai hanya tersisa dua state — state awal dan state akhir. Di antara keduanya ada busur yang labelnya berupa ekspresi reguler, dan ekspresi reguler inilah hasil seluruh algoritma. Jadi, inti prosedurnya adalah menghapus state, lalu memperbaiki otomaton sehingga diperoleh otomaton yang ekuivalen.

Menghapus satu state

Cara menghapus satu state dapat kita gambarkan dengan contoh sederhana. Misalkan sebagian otomaton kita terlihat seperti ini:

dengan R_i suatu ekspresi reguler. Seperti apa otomatonnya jika state q_r kita hapus? Bayangkan kita berada di state q_i dan bertanya: string apa saja yang dapat kita hasilkan pada bagian ini? Jika kita langsung pergi dari state q_i ke state q_j, hasilnya adalah semua string yang sesuai dengan ekspresi reguler R₄.

Namun, jika kita pergi ke state q_r, kita dapat menghasilkan string berbentuk R₁. Di state q_r kita dapat berputar untuk ekspresi reguler R₂, sehingga sebenarnya kita dapat menghasilkan string berbentuk $R_1\circ (R_2^{\ast })$. Karena dari state q_r kita masih dapat sampai di state q_j, kita tambahkan lagi ekspresi reguler R₃. Secara keseluruhan, melalui jalur ini kita dapat memperoleh string berbentuk $R_1\circ (R_2^{\ast })\circ R_3$.

Sekarang kita tahu bahwa dari bagian otomaton ini dapat terbentuk string berbentuk R₄ atau berbentuk $R_1\circ (R_2^{\ast })\circ R_3$. Tentu saja hal ini dapat ditulis sebagai ekspresi reguler $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Sekarang state q_r dapat dengan mudah kita hapus sehingga hanya tersisa dua state, q_i dan q_j, dan sebagai ganti R₄ kita tuliskan ekspresi reguler yang baru saja kita peroleh:

Prosedur ini kita lakukan untuk setiap busur dari setiap state q_i ke suatu state q_j, termasuk loop, yaitu termasuk kasus q_i = q_j.

Setelah satu state dihapus, kita memperoleh otomaton yang ekuivalen — otomaton yang mengenali bahasa yang sama.

Algoritma lengkap

Inputnya adalah NFA A = ⟨Q, Σ, δ, q₀, F⟩.

1. Konversikan NFA A menjadi GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. Selanjutnya, banyaknya state dalam Z kita lambangkan dengan huruf k.
2. Jika k = 2, algoritma berakhir, dan pada busur antara state awal dan state akhir terdapat ekspresi reguler yang dihasilkan.
3. Jika k>2, pilih sembarang state q_r yang berbeda dari state awal dan state akhir, yaitu q_r ≠ q₀′ dan q_r ≠ q_f′. Kemudian buat GNFA baru Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ yang memenuhi: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ dan untuk semua q_i ∈ Q′′ ∖ {q_f′} dan semua q_j ∈ Q′′ ∖ {q₀′} berlaku $${\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). Lalu lanjutkan ke langkah 2.

Contoh

Misalkan inputnya adalah otomaton hingga berikut:

Pertama, otomaton ini kita konversi menjadi GNFA (transisi ∅ yang tidak perlu tidak kita gambarkan):

Sekarang kita terapkan bagian kedua algoritma dan menghapus salah satu simpul. Kita mulai dari simpul q₂. Simpul q₂ kita hapus, lalu kita tambahkan transisi dari state q₁ ke state q_f. Transisi ini kita beri label b(a|b)^∗, karena dari simpul q₁ kita sampai di state q₂ untuk string berbentuk b, lalu kita dapat berputar untuk a|b, sehingga diperoleh (a|b)^∗, dan akhirnya dengan aturan epsilon kita berpindah ke q_f. Di sini berlaku b(a|b)^∗ϵ = b(a|b)^∗. Kita memperoleh otomaton:

Tinggal menghapus state terakhir, q₁. Kita tambahkan busur dari state q_s ke state q_f. Bagaimana labelnya? Ke state q₁ kita sampai melalui aturan epsilon, yang dapat langsung kita abaikan. Kemudian kita dapat berputar untuk a, sehingga diperoleh ekspresi reguler a^∗. Akhirnya, melalui busur kita sampai di q_f, sehingga ekspresi tersebut masih kita sambung dengan b(a|b)^∗. Jadi, busurnya kita beri label ekspresi reguler a^∗ b(a|b)^∗.

Otomaton hanya tinggal memiliki dua state, sehingga algoritma berakhir. Pada busurnya terdapat ekspresi reguler yang dihasilkan.

Sumber

• Contoh dan penjelasan algoritma diambil dari M. Sipser: Introduction to the Theory of Computation