Peminimuman automaton

Peminimuman automaton bermaksud mencari automaton setara yang mempunyai bilangan keadaan yang paling sedikit. Automaton yang tiada keadaan lewah pun masih boleh dipermudah lagi.

Contoh

Ambil automaton berikut:

Automaton ini hanya menerima rentetan 01 dan 11. Jelas bahawa terdapat automaton yang lebih mudah dengan tiga keadaan yang menerima bahasa yang sama. Keadaan q₁ dan q₂ boleh digabungkan menjadi satu keadaan baharu {q₁, q₂}. Peralihan yang dahulunya menuju ke keadaan q₁ atau q₂ kini menuju ke keadaan baharu itu, dan begitu juga peralihan yang keluar dari q₁ dan q₂. Kita memperoleh automaton berikut:

Jelas bahawa automaton ini menerima bahasa yang sama seperti automaton sebelumnya, tetapi bilangan keadaannya lebih sedikit.

Kesetaraan keadaan

Katakan kita mempunyai automaton A = ⟨Q, Σ, δ, q₀, F⟩. Kita mentakrifkan bahasa bagi suatu keadaan q ∈ Q, ditandakan dengan L(q), sebagai

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Maksudnya, kita menukar keadaan awal automaton A daripada q₀ kepada q dan mengira bahasa yang diterima oleh automaton ini. Dengan kata lain, bahasa L(q) mengandungi semua rentetan w yang memenuhi syarat berikut: dalam automaton A, rentetan w membawa kita dari keadaan q ke keadaan akhir automaton. Jika kita kembali kepada automaton tadi, L(q₁) = {1}.

Kita katakan bahawa dua keadaan berbeza q₁ dan q₂ setara jika

$L (q_{1}) = L (q_{2})$

Apakah maksudnya? Jika keadaan q₁, q₂ setara, kedua-duanya menjana bahasa yang sama apabila dijadikan keadaan awal automaton. Dengan kata lain: jika automaton sampai ke konfigurasi ⟨q₁, w⟩ dan ⟨q₂, w⟩, automaton itu mesti sama ada menerima rentetan dalam kedua-dua kes atau menolaknya dalam kedua-dua kes.

Kembali kepada automaton tadi: keadaan q₁ dan q₂ setara kerana jika kita berada pada keadaan q₁, kita hanya boleh menerima rentetan input jika bahagian rentetan yang belum dibaca sama dengan 1. Hal yang sama berlaku jika kita berada pada keadaan q₂.

Jadi, peminimuman automaton bertujuan mencari keadaan setara dan menghapuskannya dengan menggabungkannya menjadi satu keadaan baharu, seperti yang kita lakukan dalam contoh di atas.

Cara mencari keadaan setara

Keadaan manakah yang pasti tidak setara? Keadaan akhir dan keadaan bukan akhir pasti tidak setara kerana bahasa bagi keadaan akhir berbeza daripada bahasa bagi keadaan bukan akhir — keadaan akhir pasti menerima rentetan ε, manakala keadaan bukan akhir tidak. Mari kita terus melihat caranya melalui contoh. Katakan kita mempunyai automaton berikut:

Kita mulakan dengan membina dua set keadaan

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Sekarang kita membina jadual peralihan dan mengekalkan maklumat tentang kumpulan S₁ dan S₂:

$\begin{array}{ccccc} kumpulan & keadaan & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Kemudian kita ubah jadual ini: daripada menulis keadaan yang dituju bagi setiap simbol, kita hanya mencatat kumpulan yang dituju. Contohnya, dari keadaan q₃, bagi 0 kita sampai ke keadaan q₅, yang berada dalam kumpulan S₂. Jadi, kita tulis S₂ dalam jadual menggantikan q₅:

$\begin{array}{ccccc} kumpulan & keadaan & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Sekarang kita membahagikan kedua-dua kumpulan dengan lebih lanjut. Kita meletakkan dalam kumpulan yang sama keadaan-keadaan yang menuju ke kumpulan yang sama bagi semua simbol. Contohnya, keadaan q₃ dan q₆ tidak berada dalam kumpulan yang sama kerana kedua-duanya tidak menuju ke kumpulan yang sama, sama ada bagi 0 mahupun bagi 1. Sebaliknya, keadaan q₁ dan q₂ berada dalam kumpulan yang sama kerana kedua-duanya tiada peralihan bagi 0, dan bagi 1 kedua-duanya menuju ke kumpulan S₁. Kita membina kumpulan baharu seperti berikut:

$\begin{array}{ccccc} kumpulan & keadaan & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Dalam setiap kumpulan, peralihannya sama. Kita namakan kumpulan baharu ini dan sekali lagi menentukan kumpulan baharu yang dituju oleh setiap keadaan:

$\begin{array}{ccccc} kumpulan & keadaan & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

Pada ketika ini kita membahagikan kumpulan sekali lagi. Namun, kita lihat bahawa pembahagian lanjut tidak mungkin lagi kerana kita akan memperoleh kumpulan yang sama — keadaan q₁ dan q₂ memang mempunyai peralihan yang sama dari segi kumpulan, tetapi kedua-duanya sudah berada dalam kumpulan yang sama dan tiada keadaan lain dalam kumpulan S₄. Algoritma mencari keadaan setara telah selesai. Daripada setiap kumpulan kita cukup memilih satu keadaan dan memadamkan keadaan yang lain. Semua peralihan yang dahulunya menuju ke keadaan yang dipadamkan kini menuju ke keadaan yang dipilih itu.

Oleh itu, kita boleh memilih keadaan q₃, q₆, q₀, q₁, q₄ untuk automaton baharu kita dan membuang keadaan q₂ dan q₅. Semua peralihan yang dahulunya menuju ke q₂ kini menuju ke q₁, dan semua peralihan yang dahulunya menuju ke q₅ kini menuju ke q₄:

Langkah peminimuman automaton

Buang keadaan tak tercapai,
buang keadaan lewah,
buang keadaan setara.

Sumber

Kandungan: Keadaan tak tercapai, Keadaan lewah, Peminimuman automaton

« Artikel sebelumnya: Keadaan lewah

Artikel seterusnya: Sifat tertutup bahasa nalar »