State berlebih

Otomaton hingga dapat memiliki state yang darinya kita tidak mungkin sampai di state akhir, sehingga state tersebut tidak berguna. State seperti ini disebut state berlebih. Biasanya kita ingin menghapus state seperti ini, karena state tersebut hanya membuat otomaton menjadi rumit tanpa alasan.

Contoh state berlebih

Misalkan ada otomaton hingga berikut:

Terlihat bahwa begitu kita sampai di state q₄ atau q₅, kita tidak akan pernah berhasil mencapai salah satu state akhir, yaitu q₁ atau q₂. Jadi, state tersebut berlebih dan dapat dihapus begitu saja. Hasilnya adalah otomaton baru yang tetap ekuivalen, yaitu menerima bahasa yang sama. Setelah state berlebih dihapus, otomatonnya terlihat seperti ini:

Otomaton ini tetap menerima bahasa yang sama. Namun, ada kalanya kita justru perlu memiliki state berlebih — misalnya ketika mengonstruksi otomaton lengkap.

Definisi state berlebih

Misalkan ada otomaton hingga A = ⟨Q, Σ, δ, q₀, F⟩. State q ∈ Q disebut berlebih jika tidak ada string w ∈ Σ^∗ dan tidak ada state q_f ∈ F sedemikian sehingga

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

Cara menghapus state berlebih

Kita asumsikan bahwa inputnya adalah otomaton A = ⟨Q, Σ, δ, q₀, F⟩ yang sudah tidak memiliki state tak tercapai. Kita akan mencari satu per satu state yang mengarah ke state akhir, lalu state yang mengarah ke state yang mengarah ke state akhir, dan begitu terus. Dengan cara ini, kita memperoleh himpunan semua state yang tidak berlebih. Pada awalnya, kita tetapkan S₀ = F. Himpunan-himpunan berikutnya S_i untuk i ∈ ℕ kita konstruksi dengan aturan berikut:

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

Himpunan semua state yang tidak berlebih dapat dinyatakan sebagai berikut:

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

Himpunan state berlebih dapat dinyatakan sebagai

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

Dengan kata lain, jika berlaku S_i = S_{i + 1}, himpunan Q ∖ S_i memuat state-state berlebih. Prosedurnya akan kita ilustrasikan pada otomaton berikut:

Pertama, kita tetapkan S₀ = {q₁, q₂}. Selanjutnya, kita susun himpunan S₁ dengan menambahkan ke himpunan S₀ semua state yang mengarah ke salah satu state dalam himpunan S₀. Jadi, kita menambahkan state q₀ dan q₃, karena dari q₀ ada transisi ke q₁ dan dari q₃ ada transisi ke q₂. Diperoleh S₁ = {q₀, q₁, q₂, q₃}. Karena S₀ ≠ S₁, kita lanjutkan.

Kita susun himpunan S₂. Kita cari semua state yang darinya kita dapat sampai di S₁ dan yang belum ada di S₁. Hanya ada satu state seperti itu, yaitu q₆, yang darinya kita dapat sampai di state q₃. Diperoleh S₂ = {q₀, q₁, q₂, q₃, q₆}. Karena S₁ ≠ S₂, kita lanjutkan.

Kita susun himpunan S₃. Apakah ada state baru yang darinya kita dapat sampai di salah satu state dalam S₂? Tidak ada. Dari state q₄ dan q₅ kita tidak dapat sampai di state mana pun dalam S₂, sedangkan state lainnya sudah ada di S₂. Jadi, berlaku S₃ = {q₀, q₁, q₂, q₃, q₆}. Karena S₂ = S₃, algoritma berakhir, dan himpunan S₂ adalah himpunan state yang tidak berlebih. Himpunan {q₄, q₅} adalah himpunan state yang berlebih.

Secara formal, otomaton ekuivalen baru tanpa state berlebih dikonstruksi sebagai berikut. Untuk otomaton A = ⟨Q, Σ, δ, q₀, F⟩ kita susun otomaton ekuivalen A′ = ⟨Q′, Σ, δ′, q₀, F⟩ tanpa state berlebih.

• $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 terdefinisi

Sumber

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