Düzenli İfadenin Otomata Dönüştürülmesi

Herhangi bir düzenli ifadeyi deterministik olmayan sonlu otomata nasıl dönüştüreceğimizi göstereceğiz.

Örnek

Algoritmanın kendisini anlatmadan önce, neyin peşinde olduğumuzu bir örnekle görelim. Şu düzenli ifadeyi ele alalım: a(b|c)x^∗. Bu düzenli ifadenin ürettiği dili sözle şöyle anlatırız: “a” harfiyle başlayan, ardından “b” ya da “c” harfinin geldiği ve sonra istenen sayıda “x” harfinin geldiği sözcükler. Bu dili kabul eden bir otomat kurabilir miyiz? Elbette, şuna bak:

Bu otomatın aynı dili kabul ettiği açık. Akla şu soru geliyor: her düzenli ifade için o dili kabul eden bir otomat var mıdır? Evet, vardır.

Düzenli İfadeyi Otomata Dönüştürme Algoritması

Girişte bir R düzenli ifadesi olduğunu varsayıyoruz. Düzenli ifadeler konusundan düzenli ifadenin toplam altı farklı biçimde olabileceğini biliyoruz. Bu yüzden altı farklı durumu ayırırız:

1. Bir a ∈ Σ sembolü için R = a. Yani düzenli ifade, üzerinde çalıştığımız Σ alfabesinden yalnızca bir semboldür. Tek bir a sembolünü kabul eden otomat şöyle görünür:

   

2. R = ϵ, boş sözcük. Boş sözcüğü kabul eden otomat şöyle görünür:

   

3. R = ∅, boş dili üreten düzenli ifade. Böyle bir dili tanıyan otomat şudur:

   

4. R = R₁ ∪ R₂, burada R₁, R₂ düzenli ifadelerdir. Düzenli dillerin birleşiminin yine düzenli bir dil olduğunu ve böyle bir dili kabul eden otomatı kurabileceğimizi zaten biliyoruz. Başka bir deyişle R₁ ve R₂ ifadelerinin ürettiği dilleri tanıyan otomatlarımız olduğunu varsayıyoruz ve bunlardan yararlanarak R₁ ∪ R₂ ifadesinin ürettiği dili kabul eden otomatı kuruyoruz. Örnek: R₁ = a ve R₂ = ϵ ise yönteme göre şu otomatı elde ederiz:

   

5. R = R₁ ∘ R₂, burada R₁, R₂ düzenli ifadelerdir. Önceki maddeyle aynı durum. Düzenli dillerin birleştirilmesi düzenli bir dildir, dolayısıyla böyle bir dili kabul edecek otomatı kurabiliriz. Yani R₁ = a, R₂ = b ise birleştirme şöyle görünürdü:

   

6. $R=(R_1^{\ast })$, burada R₁ bir düzenli ifadedir. Yine düzenli bir dilin Kleene kapanışının düzenli bir dil olduğunu biliyoruz. Dolayısıyla R = a^∗ ise otomat şöyle görünürdü:

   

Bu maddeleri sırayla uygulayarak düzenli ifadenin tamamını sonlu otomata dönüştürürüz.

Kapsamlı Örnek

(a|bc)^∗ düzenli ifadesini dönüştürmeyi deneyelim. Sırayla şu otomatları elde ederiz:

Elde edilen bu otomat, (a|bc)^∗ düzenli ifadesinin ürettiği dili kabul eder. Elbette otomat son derece karmaşık ve aynı dili kabul eden çok daha basit bir otomat olduğundan hiç kuşku yok. NSO’dan DSO’ya dönüştürme algoritmasını kullanabilir, ardından otomatı en küçük hâle getirebiliriz.

Kaynaklar

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