Minimisasi otomaton

Minimisasi otomaton berarti mencari otomaton ekuivalen yang memuat state sesedikit mungkin. Otomaton yang tidak memuat state berlebih pun masih dapat disederhanakan.

Contoh

Perhatikan otomaton berikut:

Otomaton ini hanya menerima string 01 dan 11. Jelas ada otomaton yang lebih sederhana dengan tiga state yang menerima bahasa yang sama. State q₁ dan q₂ dapat digabung menjadi satu state baru {q₁, q₂}. Transisi yang tadinya menuju state q₁ atau q₂ akan menuju state baru, begitu pula transisi yang keluar dari q₁ dan q₂. Kita memperoleh otomaton berikut:

Jelas otomaton ini menerima bahasa yang sama dengan otomaton sebelumnya, tetapi memiliki lebih sedikit state.

State ekuivalen

Misalkan ada otomaton A = ⟨Q, Σ, δ, q₀, F⟩. Bahasa state q ∈ Q, dilambangkan dengan L(q), didefinisikan sebagai

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

Artinya, kita mengganti state awal otomaton A dari q₀ menjadi q, lalu menentukan bahasa yang diterima otomaton ini. Dengan kata lain, bahasa L(q) memuat semua string w sedemikian sehingga pada otomaton A string w membawa kita dari state q ke state akhir. Jika kita kembali ke otomaton sebelumnya, L(q₁) = {1}.

Dua state berbeda q₁ dan q₂ disebut ekuivalen jika berlaku

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

Apa artinya? Jika state q₁, q₂ ekuivalen dan masing-masing kita jadikan state awal otomaton, keduanya akan menghasilkan bahasa yang sama. Dengan kata lain, jika otomaton sampai di konfigurasi ⟨q₁, w⟩ dan ⟨q₂, w⟩, otomaton harus menerima string pada kedua kasus atau menolaknya pada kedua kasus.

Kembali ke otomaton sebelumnya: state q₁ dan q₂ ekuivalen, karena jika kita berada di state q₁, string input hanya dapat diterima jika bagian string yang belum dibaca sama dengan 1. Hal yang sama berlaku jika kita berada di state q₂.

Jadi, minimisasi otomaton bertujuan mencari state-state ekuivalen dan menghilangkannya dengan menggabungkan state-state tersebut menjadi satu state baru, seperti yang kita lakukan pada contoh di atas.

Cara mencari state ekuivalen

State mana yang pasti tidak ekuivalen? State akhir dan state bukan akhir pasti tidak ekuivalen, karena bahasa state akhir berbeda dari bahasa state bukan akhir — state akhir pasti menerima string ε, sedangkan state bukan akhir tidak. Prosedurnya langsung kita tunjukkan pada contoh. Misalkan ada otomaton berikut:

Kita mulai dengan membuat dua himpunan state

$\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 buat tabel transisi dan tetap mencatat informasi tentang kelompok S₁ dan S₂:

$\begin{array}{ccccc} kelompok & state & 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}$

Sekarang tabel kita ubah: alih-alih menuliskan state tujuan untuk setiap simbol, kita hanya mencatat kelompok tujuannya. Misalnya, dari state q₃ untuk 0 kita sampai di state q₅, yang termasuk kelompok S₂. Jadi, sebagai ganti q₅, kita tuliskan S₂ ke dalam tabel:

$\begin{array}{ccccc} kelompok & state & 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 kedua kelompok kita bagi lagi. Ke dalam kelompok yang sama selalu kita masukkan state-state yang untuk semua simbol berpindah ke kelompok yang sama. Misalnya, state q₃ dan q₆ tidak berada di kelompok yang sama, karena baik untuk 0 maupun untuk 1 keduanya tidak menuju kelompok yang sama. Sebaliknya, state q₁ dan q₂ berada di kelompok yang sama, karena keduanya tidak memiliki transisi untuk 0 dan keduanya menuju kelompok S₁ untuk 1. Jadi, kita membuat kelompok-kelompok baru:

$\begin{array}{ccccc} kelompok & state & 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 kelompok, transisinya sama. Kelompok-kelompok yang baru terbentuk kita beri nama, lalu kita cari lagi ke kelompok baru mana state-state tersebut mengarah:

$\begin{array}{ccccc} kelompok & state & 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 titik ini, kita lakukan pembagian kelompok berikutnya. Namun, terlihat bahwa kita tidak dapat membagi lebih jauh lagi, karena kita akan memperoleh kelompok yang sama — state q₁ dan q₂ memang memiliki transisi yang sama dalam hal kelompok, tetapi keduanya sudah berada di kelompok yang sama, dan tidak ada state lain di kelompok S₄. Algoritma pencarian state ekuivalen selesai. Dari setiap kelompok, cukup kita pilih satu state, state lainnya kita hapus, dan semua transisi yang tadinya menuju state yang dihapus diarahkan ke satu state yang kita pilih.

Jadi, kita dapat memilih agar otomaton baru kita memiliki state q₃, q₆, q₀, q₁, q₄, sedangkan state q₂ dan q₅ kita hapus. Semua transisi yang tadinya menuju q₂ sekarang menuju q₁, dan semua transisi yang tadinya menuju q₅ sekarang menuju q₄:

Langkah-langkah minimisasi otomaton

Hapus state tak tercapai,
hapus state berlebih,
hapus state ekuivalen.

Sumber

Daftar isi: State tak tercapai, State berlebih, Minimisasi otomaton

« Artikel sebelumnya: State berlebih

Artikel berikutnya: Sifat ketertutupan bahasa reguler »