Keadaan lewah

Automaton terhingga boleh mempunyai keadaan yang tidak mungkin membawa ke keadaan akhir, jadi keadaan itu tidak berguna. Keadaan sebegini dipanggil keadaan lewah. Biasanya kita mahu membuang keadaan ini kerana keadaan ini hanya merumitkan automaton tanpa sebarang faedah.

Contoh keadaan lewah

Katakan kita mempunyai automaton terhingga berikut:

Kita lihat bahawa sebaik sahaja kita sampai ke keadaan q₄ atau q₅, kita tidak akan dapat sampai ke salah satu keadaan akhir q₁ atau q₂. Oleh itu, keadaan ini lewah dan boleh dibuang begitu sahaja. Hasilnya ialah automaton baharu yang setara, iaitu automaton yang menerima bahasa yang sama. Selepas keadaan lewah dipadamkan, automaton itu kelihatan seperti berikut:

Automaton ini tetap menerima bahasa yang sama. Namun, ada kalanya keadaan lewah memang berguna — misalnya apabila kita membina automaton lengkap.

Takrif keadaan lewah

Katakan kita mempunyai automaton terhingga A = ⟨Q, Σ, δ, q₀, F⟩. Kita katakan bahawa keadaan q ∈ Q lewah jika tidak wujud sebarang rentetan w ∈ Σ^∗ dan sebarang keadaan q_f ∈ F yang memenuhi

$$⟨q,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩.$$

Cara membuang keadaan lewah

Kita anggap bahawa input ialah automaton A = ⟨Q, Σ, δ, q₀, F⟩ yang sudah tiada keadaan tak tercapai. Kita mencari keadaan yang menuju ke keadaan akhir satu demi satu, kemudian keadaan yang menuju ke keadaan yang menuju ke keadaan akhir, dan begitulah seterusnya. Dengan cara ini kita memperoleh set semua keadaan yang tidak lewah. Pada mulanya kita tetapkan S₀ = F. Kita membina set seterusnya S_i bagi i ∈ ℕ mengikut peraturan berikut:

$$S_i=\{q\in Q|\mathrm{\exists }a\in \mathrm{\Sigma }:\delta (q,a)\in S_{i-1}\}\cup S_{i-1}$$

Set semua keadaan yang tidak lewah yang terhasil boleh dinyatakan seperti berikut:

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

Set keadaan lewah pula ialah

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

Dengan kata lain: jika S_i = S_{i + 1}, maka set Q ∖ S_i mengandungi keadaan lewah. Kita menggambarkan langkah-langkahnya dengan automaton berikut:

Pertama sekali, kita tetapkan S₀ = {q₁, q₂}. Seterusnya kita membina set S₁ dengan menambahkan kepada set S₀ semua keadaan yang menuju ke salah satu keadaan dalam set S₀. Jadi, kita menambahkan keadaan q₀ dan q₃ kerana terdapat peralihan dari q₀ ke q₁ dan dari q₃ ke q₂. Kita memperoleh S₁ = {q₀, q₁, q₂, q₃}. Oleh sebab S₀ ≠ S₁, kita teruskan.

Kita membina set S₂. Kita mencari semua keadaan yang boleh menuju ke S₁ tetapi belum berada dalam S₁. Hanya ada satu keadaan sebegini, iaitu q₆, yang boleh menuju ke keadaan q₃. Kita memperoleh S₂ = {q₀, q₁, q₂, q₃, q₆}. Oleh sebab S₁ ≠ S₂, kita teruskan.

Kita membina set S₃. Adakah terdapat keadaan baharu yang boleh menuju ke mana-mana keadaan dalam S₂? Tiada. Dari keadaan q₄ dan q₅ kita tidak dapat sampai ke mana-mana keadaan dalam S₂, dan keadaan yang lain sudah berada dalam S₂. Oleh itu, S₃ = {q₀, q₁, q₂, q₃, q₆}. Oleh sebab S₂ = S₃, algoritma berakhir, dan set S₂ ialah set keadaan yang tidak lewah. Set {q₄, q₅} ialah set keadaan yang lewah.

Secara formal, automaton setara baharu tanpa keadaan lewah dibina seperti berikut. Kita mempunyai automaton A = ⟨Q, Σ, δ, q₀, F⟩ dan membina automaton setara A′ = ⟨Q′, Σ, δ′, q₀, F⟩ tanpa keadaan lewah.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a) jika δ(q, a) ∈ Q′; jika tidak, δ′(q, a) tidak ditakrifkan

Sumber

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools