Keadaan tak tercapai

Automaton terhingga boleh mempunyai keadaan yang tidak mungkin dicapai. Keadaan sebegini dipanggil keadaan tak tercapai. Biasanya kita mahu membuang keadaan ini kerana keadaan ini hanya merumitkan automaton tanpa sebarang faedah.

Contoh keadaan tak tercapai

Katakan kita mempunyai automaton berikut:

Kita lihat bahawa walau apa pun yang kita lakukan, kita tidak akan sampai ke keadaan q₃ kerana tiada peralihan yang menuju kepadanya. Oleh itu, kita katakan bahawa keadaan q₃ tak tercapai. Persoalannya, adakah keadaan q₃ boleh dicapai jika ada peralihan dari keadaan lain yang menuju kepadanya? Jika kita melukis anak panah dari salah satu keadaan q₀, q₁, q₂, q₅, keadaan itu boleh dicapai. Jika kita menambahkan satu lagi nod dan melukis peralihan daripadanya…

…sudah tentu kedua-dua keadaan q₃ dan q₄ tak tercapai.

Takrif keadaan tak tercapai

Pertama sekali, kita mentakrifkan keadaan yang boleh dicapai. Katakan kita mempunyai automaton terhingga A = ⟨Q, Σ, δ, q₀, F⟩. Kita katakan bahawa keadaan q ∈ Q boleh dicapai jika wujud rentetan w ∈ Σ^∗ yang memenuhi

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

Keadaan q ∈ Q tak tercapai jika keadaan itu tidak boleh dicapai.

Cara membuang keadaan tak tercapai

Jika automaton sudah mempunyai keadaan tak tercapai, sebaiknya keadaan itu dibuang. Kita membina automaton setara A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ yang tiada keadaan tak tercapai.

Kita membina set keadaan yang boleh dicapai secara berlelaran. Kita bermula dengan set S₀ = {q₀} kerana keadaan awal pasti boleh dicapai. Set seterusnya dibina seperti berikut:

$$S_i=\{r|\delta (q,a)=r\text{ bagi suatu }q\in S_{i-1},a\in \mathrm{\Sigma }\}\cup S_{i-1}$$

Dengan kata mudah, set S₀ sentiasa diberikan. Set S₁ dibina dengan mengambil semua keadaan dalam set S₀ dan mencari semua keadaan yang dituju oleh peralihan bagi semua simbol daripada Σ. Keadaan ini digabungkan (kesatuan) dengan set keadaan asal S₀. Dengan cara yang sama kita mencari set S₂ dan seterusnya. Jelas bahawa S_{i − 1} ⊆ S_i.

Set keadaan yang boleh dicapai kemudiannya diperoleh seperti berikut:

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

Mungkin kelihatan pelik bahawa kita cuba mencari kesatuan bagi set S_i yang tak terhingga banyaknya, tetapi automaton hanya mengandungi bilangan keadaan yang terhingga. Ini bermakna pada suatu ketika, set S_j, S_{j + 1} dan semua set seterusnya akan sama. Jadi, walaupun kita mengambil kesatuan bagi set yang tak terhingga banyaknya, kita boleh memperoleh set keadaan yang terhingga.

Mari kita kembali kepada automaton

dan cuba mencari set keadaan yang boleh dicapai. Kita bermula dengan menetapkan kesamaan asas

$$S_0=\left\{q_0\right\}$$

Sekarang kita mengira set S₁. Kita perlu mencari semua peralihan dari keadaan q₀ dan menambahkan keadaan sasarannya kepada set S₀. Oleh sebab q₀ → ^a q₁ dan q₀ → ^bq₂, set S₁ juga mengandungi keadaan q₁ dan q₂:

$$S_1=\{q_0,q_1,q_2\}$$

Seterusnya kita membina set S₂. Kita lihat ke mana sahaja kita boleh pergi dari keadaan q₀, q₁, q₂. Satu-satunya keadaan baharu ialah q₅, yang boleh dicapai dari keadaan q₁:

$$S_2=\{q_0,q_1,q_2,q_5\}$$

Kemudian kita membina set S₃. Bolehkah kita sampai ke keadaan baharu dari keadaan q₀, q₁, q₂, q₅? Tidak boleh, jadi set S₃ mengandungi unsur yang sama seperti S₂:

$$S_3=\{q_0,q_1,q_2,q_5\}$$

Oleh sebab S₂ = S₃, maka S₃ = S₄ = S₅ = … juga. Jika kita mengambil kesatuan semua S_i, kita memperoleh set S₂ kerana tiada unsur baharu yang ditambahkan dalam set seterusnya.

Oleh itu, set keadaan yang boleh dicapai bagi automaton ini ialah {q₀, q₁, q₂, q₅}. Keadaan tak tercapai diperoleh dengan beza set yang mudah:

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

Set keadaan tak tercapai bagi automaton kita ialah {q₃, q₄}. Kita membuang semua keadaan tak tercapai daripada automaton A serta semua peralihan yang melibatkan keadaan tak tercapai. Maksudnya, automaton A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ tanpa keadaan tak tercapai yang setara dengan automaton A = ⟨Q, Σ, δ, q₀, F⟩ ditakrifkan sebagai:

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

Sumber

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