Gereksiz Durumlar

Sonlu otomatın bazı durumlarından kabul durumuna ulaşmak mümkün olmayabilir; bu durumlar boşuna yer kaplar. Bunlara gereksiz durumlar diyoruz. Bu durumları genellikle çıkarmak isteriz, çünkü otomatı yalnızca gereksiz yere karmaşıklaştırırlar.

Gereksiz Durumlara Örnek

Şu sonlu otomatı ele alalım:

q₄ ya da q₅ durumuna girdiğimiz anda kabul durumlarından q₁ ve q₂’ye bir daha asla ulaşamayız. Bu durumlar gereksizdir ve onları çıkarabiliriz; böylece denk bir otomat elde ederiz, yani aynı dili kabul eden bir otomat. Gereksiz durumlar silindikten sonra otomat şöyle görünür:

Otomat yine aynı dili kabul eder. Yine de bazı gereksiz durumları tutmanın yerinde olduğu anlar vardır — örneğin tam otomat kurarken.

Gereksiz Durumun Tanımı

A = ⟨Q, Σ, δ, q₀, F⟩ sonlu otomat olsun. Şu koşulu sağlayan hiçbir w ∈ Σ^∗ sözcüğü ve hiçbir q_f ∈ F durumu yoksa q ∈ Q durumuna gereksiz diyoruz:

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

Gereksiz Durumlar Nasıl Çıkarılır

Girişte, ulaşılamayan durumları zaten olmayan bir A = ⟨Q, Σ, δ, q₀, F⟩ otomatı olduğunu varsayıyoruz. Önce kabul durumlarına giden durumları, sonra kabul durumlarına giden durumlara giden durumları ve bunu böyle sürdürerek durumları adım adım buluruz. Böylece gereksiz olmayan tüm durumların kümesini elde ederiz. Başlangıçta S₀ = F alırız. Sonraki S_i kümelerini (i ∈ ℕ⁺ için) şu kurala göre kuracağız:

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

Gereksiz olmayan tüm durumların kümesini şöyle yazabiliriz:

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

Gereksiz durumların kümesini ise şöyle:

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

Başka bir deyişle, S_i = S_{i + 1} ise Q ∖ S_i kümesi gereksiz durumları içerir. Yöntemi şu otomat üzerinde göstereceğiz:

Önce S₀ = {q₁, q₂} alırız. Sonra S₁ kümesini şöyle kurarız: S₀ kümesine, S₀ içindeki durumlardan birine giden tüm durumları ekleriz. q₀ ve q₃ durumlarını ekleriz, çünkü q₀ durumundan q₁ durumuna, q₃ durumundan q₂ durumuna geçiş vardır. S₁ = {q₀, q₁, q₂, q₃} elde ederiz. S₀ ≠ S₁ olduğu için devam ederiz.

S₂ kümesini kuralım. Kendisinden S₁ kümesine ulaşılabilen ve henüz S₁ içinde olmayan tüm durumları ararız. Böyle tek bir durum vardır: q₃ durumuna gidilebilen q₆. S₂ = {q₀, q₁, q₂, q₃, q₆} elde ederiz. S₁ ≠ S₂ olduğu için devam ederiz.

S₃ kümesini kuralım. S₂ içindeki durumlardan birine gidebilen yeni bir durum var mı? Yok: q₄ ve q₅ durumlarından S₂ içindeki hiçbir duruma gidilemez, diğer durumlar zaten S₂ içindedir. Dolayısıyla S₃ = {q₀, q₁, q₂, q₃, q₆} olur. S₂ = S₃ olduğu için algoritma sona erer ve S₂ kümesi gereksiz olmayan durumların kümesidir. {q₄, q₅} kümesi ise gereksiz olan durumların kümesidir.

Gereksiz durumları olmayan yeni denk otomatı biçimsel olarak şöyle kurarız. A = ⟨Q, Σ, δ, q₀, F⟩ otomatı verilmiş olsun; ona denk, gereksiz durumları olmayan A′ = ⟨Q′, Σ, δ′, q₀, F⟩ otomatını kuralım.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a), eğer δ(q, a) ∈ Q′ ise; aksi hâlde δ′(q, a) tanımlı değildir

Kaynaklar

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