✖

State tak tercapai

Otomaton hingga dapat memiliki state yang tidak mungkin dicapai. State seperti ini disebut state tak tercapai. Biasanya kita ingin menghapus state seperti ini, karena state tersebut hanya membuat otomaton menjadi rumit tanpa alasan.

Contoh state tak tercapai

Misalkan ada otomaton berikut:

Terlihat bahwa apa pun yang kita lakukan, kita tidak akan pernah sampai di state q3, karena tidak ada transisi yang menuju ke sana. Karena itu, state q3 disebut tak tercapai. Pertanyaannya, apakah state q3 menjadi tercapai jika ada transisi dari state lain yang menuju ke sana? Jika kita menambahkan busur dari salah satu state q0, q1, q2, q5, state tersebut menjadi tercapai. Jika kita menambahkan simpul lain dan membuat transisi dari simpul tersebut…

…tentu saja kedua state, q3 maupun q4, tetap tak tercapai.

Definisi state tak tercapai

Pertama, kita definisikan state tercapai. Misalkan ada otomaton hingga A = ⟨Q, Σ, δ, q0, F⟩. State q ∈ Q disebut tercapai jika ada string w ∈ Σ∗ sedemikian sehingga

⟨q0,w⟩↦∗⟨q,ε⟩.

State q ∈ Q disebut tak tercapai jika state tersebut tidak tercapai.

Cara menghapus state tak tercapai

Jika otomaton sudah memiliki state tak tercapai, sebaiknya state tersebut dihapus. Kita susun otomaton ekuivalen A′ = ⟨Q′, Σ, δ′, q0, F′⟩ yang tidak memiliki state tak tercapai.

Himpunan state tercapai kita susun secara iteratif. Kita mulai dengan himpunan S0 = {q0}, karena state awal pasti tercapai. Himpunan berikutnya kita susun sebagai berikut:

Si={r|δ(q,a)=r untuk suatu q∈Si−1,a∈Σ}∪Si−1

Dengan kata lain, himpunan S0 selalu sudah diketahui. Himpunan S1 kita susun dengan mengambil semua state dari himpunan S0 dan mencari ke mana saja transisi untuk semua simbol dari Σ mengarah. State-state ini kita gabungkan dengan himpunan state semula S0. Dengan cara yang sama, kita mencari himpunan S2 dan seterusnya. Jelas berlaku Si − 1 ⊆ Si.

Himpunan state tercapai kemudian dapat diperoleh sebagai berikut:

⋃i=1∞Si

Mungkin terlihat aneh bahwa kita menggabungkan tak hingga banyaknya himpunan Si, padahal otomaton hanya memiliki state yang banyaknya berhingga. Artinya, pada suatu saat himpunan Sj, Sj + 1, dan semua himpunan berikutnya akan sama, sehingga gabungan tak hingga banyaknya himpunan pun dapat menghasilkan himpunan state yang berhingga.

Kita kembali ke otomaton

dan mencoba mencari himpunan state tercapai. Kita mulai dengan menetapkan kesamaan dasar

S0={q0}

Sekarang kita hitung himpunan S1. Kita harus mencari semua transisi dari state q0 dan menambahkan state tujuannya ke himpunan S0. Karena berlaku q0 → a q1 dan q0 → bq2, himpunan S1 juga memuat state q1 dan q2:

S1={q0,q1,q2}

Selanjutnya, kita konstruksi himpunan S2. Kita lihat ke mana saja kita dapat sampai dari state q0, q1, q2. Satu-satunya state baru adalah q5, yang dapat dicapai dari state q1:

S2={q0,q1,q2,q5}

Kemudian kita susun himpunan S3. Apakah dari state q0, q1, q2, q5 kita dapat sampai di state baru? Tidak bisa, sehingga himpunan S3 memuat anggota yang sama dengan S2:

S3={q0,q1,q2,q5}

Karena S2 = S3, berlaku juga S3 = S4 = S5 = … Jika semua Si kita gabungkan, kita memperoleh himpunan S2, karena tidak ada anggota baru yang bertambah di himpunan mana pun berikutnya.

Jadi, himpunan state tercapai pada otomaton ini adalah {q0, q1, q2, q5}. State tak tercapai diperoleh dengan selisih himpunan biasa:

Q∖⋃i=1∞Si

Himpunan state tak tercapai pada otomaton kita adalah {q3, q4}. Dari otomaton A kita hapus semua state tak tercapai beserta semua transisi yang melibatkan state tak tercapai. Artinya, otomaton ekuivalen tanpa state tak tercapai A′ = ⟨Q′, Σ, δ′, q0, F′⟩ untuk otomaton A = ⟨Q, Σ, δ, q0, F⟩ didefinisikan sebagai:

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
  • F′=F∩Q′=F∩⋃i=1∞Si

Sumber

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