Otomatın Düzenli İfadeye Dönüştürülmesi

Herhangi bir sonlu otomatı düzenli ifadeye nasıl dönüştüreceğimizi göstereceğiz.

Algoritmanın Anlatımı

Girişte bir A NSO’su var. Önce onu GNSO’ya çeviririz. İkinci aşamada her adımda bir durumu ortadan kaldırır, geçiş fonksiyonunu uygun biçimde değiştirir ve yalnızca iki durum kalana kadar — başlangıç ve kabul durumu — bunu tekrarlarız. Bu ikisi arasında, etiketi düzenli bir ifade olan bir geçiş kalır ve bu ifade algoritmanın sonucudur. Yani işlemin özü, bir durumu ortadan kaldırmak ve ardından otomatı denk kalacak biçimde düzeltmektir.

Bir Durumu Ortadan Kaldırma

Bir durumun nasıl ortadan kaldırılacağını basit bir örnekle gösterebiliriz. Otomatımızın bir kısmının şöyle göründüğünü varsayalım:

burada R_i birer düzenli ifadedir. q_r durumunu kaldırırsak otomat nasıl görünür? Şöyle düşünebiliriz: q_i durumundayız ve şunu soruyoruz: bu kesimde hangi sözcükleri üretebiliriz? q_i durumundan doğrudan q_j durumuna gidersek, bunlar R₄ düzenli ifadesine uyan tüm sözcükler olur.

Ama q_r durumuna gidersek R₁ biçimindeki sözcükleri üretebiliriz. q_r durumunda ise R₂ düzenli ifadesi için döngüde kalabiliriz, yani aslında $R_1\circ (R_2^{\ast })$ biçimindeki sözcükleri üretebiliriz. q_r durumundan q_j durumuna da geçebildiğimiz için buraya R₃ düzenli ifadesini de ekleriz. Böylece bu yoldan $R_1\circ (R_2^{\ast })\circ R_3$ biçimindeki sözcükleri elde edebiliriz.

Demek ki otomatın bu kısmından R₄ biçiminde ya da $R_1\circ (R_2^{\ast })\circ R_3$ biçiminde sözcükler oluşabilir. Bunu elbette düzenli ifade olarak $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$ biçiminde yazabiliriz.

Artık q_r durumunu kolayca kaldırıp yalnızca q_i ve q_j durumlarını bırakabiliriz; R₄ yerine de az önce hesapladığımız düzenli ifadeyi yazarız:

Bu işlemi, her q_i durumundan bir q_j durumuna giden her geçişle yaparız; döngüler de dâhildir, yani q_i = q_j olan durum da.

Bir durumu kaldırdıktan sonra denk bir otomat elde ederiz — yani aynı dili tanıyan bir otomat.

Algoritmanın Tamamı

Girişte bir A = ⟨Q, Σ, δ, q₀, F⟩ NSO’su var.

1. A NSO’sunu Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩ GNSO’suna çeviririz. Bundan sonra Z otomatındaki durum sayısını k harfiyle göstereceğiz.
2. k = 2 ise algoritma biter ve başlangıç ile kabul durumu arasındaki geçişin etiketi elde edilen düzenli ifadedir.
3. k>2 ise başlangıç ve kabul durumundan farklı herhangi bir q_r durumu seçeriz, yani q_r ≠ q₀′ ve q_r ≠ q_f′. Sonra aşağıdaki koşulları sağlayan yeni bir Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ GNSO’su oluştururuz: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ ve her q_i ∈ Q′′ ∖ {q_f′} ile her q_j ∈ Q′′ ∖ {q₀′} için $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ olsun; burada R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Sonra 2. adımla devam et.

Örnek

Girişte şu sonlu otomat olsun:

Önce onu GNSO’ya çeviririz (gereksiz ∅-geçişlerini çizmeyeceğiz):

Şimdi algoritmanın ikinci kısmını uygulayıp bir düğümü kaldıralım. q₂ düğümüyle başlayalım. q₂ düğümünü kaldırıp q₁ durumundan q_f durumuna bir geçiş ekleriz. Bu geçişi b(a|b)^∗ ile etiketleriz, çünkü q₁ düğümünden q₂ durumuna b biçimindeki sözcüklerle gideriz, sonra a|b için döngüde kalabiliriz ve böylece (a|b)^∗ elde ederiz; en sonunda ε-geçişiyle q_f durumuna geçeriz. Burada b(a|b)^∗ϵ = b(a|b)^∗ olduğuna dikkat et. Şu otomatı elde ederiz:

Geriye son durumu, yani q₁ durumunu kaldırmak kalıyor. q_s durumundan q_f durumuna bir geçiş ekleriz. Bunu nasıl etiketleriz? q₁ durumuna ε-geçişiyle geliriz, onu doğrudan atlayabiliriz. Sonra a için döngüde kalabiliriz, böylece a^∗ düzenli ifadesini elde ederiz. En sonunda geçişle q_f durumuna ulaşırız, yani ifadeyi b(a|b)^∗ ile birleştiririz. Böylece geçişi a^∗ b(a|b)^∗ düzenli ifadesiyle etiketleriz.

Otomatın artık yalnızca iki durumu var, yani algoritma biter. Geçişin üzerindeki ifade elde edilen düzenli ifadedir.

Kaynaklar

• Örnek ve algoritmanın anlatımı M. Sipser: Introduction to the Theory of Computation kitabından alınmıştır