Yazan : Şadi Evren ŞEKER

Bu yazıda belirsiz sonlu otomattan(NFA) Belirli sonlu otomata (gerekirci sonlu otomat, nedensel sonlu otomat, deterministic finite automata) dönüştürmenin nasıl yapıldığı anlatılmaktadır.

Basitçe bir iki adımlık işlemler izlenerek bu dönüşüm gerçekleştirilebilir:

  1. Öncelikle gerekircilik (determinism) açısından birbiri ile özdeş olan kümler çıkarılmalıdır (subset construction)
  2. Bu kümelerin diğer kümler ile olan ilişkisi çıkarılmalıdır.

Sonuçta elde eden kümelerin birer durum göstermesi ve bu durumlar arası bağlantıların yukarıdaki ikinci adımda çıkarılmış ilişkisi belirli bir sonlu otomat (DFA) üretmiş olur.

Bu işlemi aşağıdaki örnekte inceleyelim:

Yukarıda belirsiz bir sonlu otomaton gösterilmiştir. Bu yapıyı belirli sonlu otomata adım adım çevirelim.

Öncelikle lambda ( ε , λ ) ile ulaşılabilen durumları sıralayalım :

{a} : A , tek elemanlı bu küme başlangıç elemanını içerir, bunun dışında yukarıdaki otomatonda herhangi bir elemana lambda ile ulaşılması söz konusu değildir.

Şimdi bir önceki adımda ürettiğimi A kümesinden gidilebilecek kelime ihtimallerini yazalım

A1 (A kümesinden 1 değeri ile ulaşılabilecek olan durumlar) : { b } : B (bu kümeye B ismini verelim)

A0 (A kümesinden 0 değeri ile ulaşılabilecek olan durumlar): { d } : C ( bu kümeye C ismini verelim)

B1 (B kümesinden 1 değeri ile ulaşılabilecek olan durumlar): {b,f} : D (bu kümeye D ismini verelim)

B0 (B kümesinden 0 değeri ile ulaşılabilecek olan durumlar): {c} : E (bu kümeye E ismini verelim)

C1 (C kümesinden 1 değeri ile ulaşılabilecek olan durumlar): {e} : F (bu kümeye F ismini verelim)

C0 (C kümesinden 0 değeri ile ulaşılabilecek olan durumlar): {c} : E (bu kümeye zaten E ismini vermiştik)

D0 (D kümesinden 0 değeri ile ulaşılabilecek olan durumlar): {c} : E (bu kümeye zaten E ismini vermiştik)

D1 (D kümesinden 1 değeri ile ulaşılabilecek olan durumlar): {e} : F (bu kümeye zaten F ismini vermiştik)

E0 (E kümesinden 0 değeri ile ulaşılabilecek olan durumlar): {f} : G (bu kümeye G ismini verelim)

E1 bu ihtimal boş kümedir dolayısıyla işlem yapılmıyor

F0 bu ihtimal boş kümedir dolayısıyla işlem yapılmıyor

F1 (F kümesinden 1 değeri ile ulaşılabilecek olan durumlar): {a,f} : H (bu kümeye H ismini verelim)

G0 bu ihtimal boş kümedir dolayısıyla işlem yapılmıyor

G1 bu ihtimal boş kümedir dolayısıyla işlem yapılmıyor

H0 (H kümesinden 0 değeri ile ulaşılabilecek olan durumlar): {d} : C (bu kümeye zaten C ismini vermiştik)

H1 (H kümesinden 1 değeri ile ulaşılabilecek olan durumlar): {b} : B (bu kümeye zaten B ismini vermiştik)

Yukarıda bulunan bütün alt kümelerin inşası tamamlandı ve bu kümelerin diğer kümelere gidiş koşulları belirlendi şimdi bu kümeler arasında yukarıda da listelenmiş olan geçişleri çizebiliriz:

Yukarıdaki yeni otomatımızın belirli (nedensel, gerekirci) olduğunu söyleyebiliriz çünkü her durumda gelen kelimeye göre gidilebilecek tek ihtimal bulunmaktadır.

Kümelerin NFA üzerinde gösterimi

Bu kısmı Tarık Bey’in sorusu üzerine ekliyorum. Yukarıdaki kümeleri graf üzerinde kırmızı büyük harf ile gösterdim. Bu sayede kümelerin takibi sanırım daha kolay olacaktır.

Yukarıdaki şekilde şaşılmaması gereken bir husus, aynı düğüme birden fazla küme ismi geliyor olmasıdır. Bu normaldir ve doğrudur ancak kümelerin birden fazla düğüm içerebildiğine dikkat etmek gerekir. Örneğin f düğümü, D,H ve G kümelerinin üyesidir. Ancak tek başına sadece G kümesine üyedir. H kümesine a düğümü ile ve D kümesine b düğümü ile üyedir.

Örnek  1

Bir düzenli ifade (regular expression) olarak aşağıdaki örnek verilmiş olsun. Bu örneği sonlu otomat (finite state automata) olarak göstermeye çalışalım:

a*b*

Yukarıdaki düzenli ifadeyi tanımak için öncelikle bu ifadeden üretilebilecek örnekleri görelim:

Üretilebilecek en kısa dizgi (String): ε (yani boş küme olacaktır, bu bazı kitaplarda λ sembolü ile de gösterilir). Çünkü kleene yıldızının üreteceği sonuçlar arasında boş küme de bulunmaktadır.

İkinci dizgimiz (String) : ab olacaktır ve bu üretme işlemi aab , abb, aabb, aaab, abbb şeklinde devam edecektir.

Yukarıdaki bu düzenli ifadeyi göstermek için aşağıdaki sonlu otomatı çizebiliriz (genelde sık yapılan bir hata olduğu için aşağıdaki hatalı örneği çizmek istiyorum):

nfaab

Yukarıdaki şekilde anlatılmak istenen tek bir durum (State) oluşudur ve bu durum hem başlangıç (okla belirtilmiştir) hem de bitiş durumu (çift çizgi ile belirtilmiştir) olduğudur. Bu durum üzerinde hem a hem de b harfleri ile istenildiği kadar dönülebilir.

Yukarıdaki hata, yukarıdai FSM’in örneğin ba gibi bir kelimeyi de kabul etmesidir. Oysaki düzenli ifademiz buna izin vermemektedir. Doğrusu aşağıdaki şekilde olmalıdır.

nfaab2

Yukarıdaki çizim doğru çizimdir. Görüldüğü üzere otomatımız hem boş kelimeyi hem de a ve b ile üretilebilecek (Sırası değişmeden) bütün kelimeleri desteklemektedir.

Yorumlar

  1. tarık

    hocam bu kısımda hata yok mu?

    “E0 (E kümesinden 0 değeri ile ulaşılabilecek olan durumlar): {f} : G (bu kümeye G ismini verelim)
    E1 bu ihtimal boş kümedir dolayısıyla işlem yapılmıyor”…

    tam tersi olması lazım.çünkü e den f ye 1 geçiyor..
    ————————————————————
    ayrıca başka bir durumda H için.G kümesine işlem yapmadığımız halde H ye niye yaptık.yani H0 VE H1 boş küme olduğu halde niye işlem yaptık ki? mesela soruda “H0 (H kümesinden 0 değeri ile ulaşılabilecek olan durumlar): {d} ,
    H1 (H kümesinden 1 değeri ile ulaşılabilecek olan durumlar): {b}” deniiyor…H0 ve H1 varlığı ortada yokki nereye işlem yaptık? anlamadım.
    bir hata var sanırım …

  2. Şadi Evren ŞEKER Article Author

    Küme ve düğüm isimlerini karıştırmamak gerekiyor. Yukarıdaki bu kümelerin sol tarafındaki isimleri düşünün.

    Yani yukarıdaki örnekte E kümesi tanımlanırken orjinal graftaki c düğümü olarak tanımlanıyor. Aslında E0 ile ifade edilen orjinal graftaki e düğümü değil c düğümüdür. Bakın E kümesinin tanımlandığı satırları okuyalım:

    Önce A1 tanımlanıyor ve bu kümeye B ismi veriliyor. Yani B kümesi a düğümünden 1 ile gidilen düğümler oluyor ki bu grafta da b düğümüne tekabül ediyor.

    Ardından B0 tanımlanıyor. Bu kümeye E ismi veriliyor. Bu da bize E kümesinin b düğümünden 0 ile gidilbebilen düğümlerini gösteriyor. Yani graftaki c düğümü E kümesi olmuş oluyor.

    Sizin sorunuza gelirsek, E0 kümesi graftaki e düğümünden 0 ile gidilen düğümleri değil, c düğümünden 0 ile gidilen düğümleri gösteriyor. Çünkü E kümesi aslında c düğümüdür.

    Burada düğümler ve kümeler karışmasın diye kümeleri büyük, düğümleri küçük harfle gösterdim. Yazıda da bu şekilde.

    Sorunuzun ikinci kısmına gelince H kümesi (dikkat edin h düğümü değil, çünkü gerçekten de h düğümü yok ama H kümesi var ve) F1 olarak tanımlanmış. F kümesi ise C1 olarak ve C kümesi ise A0 olarak tanımlanmış. Bu durumda C kümesi d
    F kümesi e
    H kümesi ise a ve f ‘den oluşuyor.
    Yani aslında H kümesi bulunuyor. Zaten DFA çizilirken de bu kümelere göre çiziliyor.

    Ben yazıya bir graf daha ekliyerek kümeleri NFA üzerinde göstermeye çalışayım belki daha iyi anlamaya yardımcı olur.

    Başarılar

  3. aysesule

    D1->{e}:F kısmında D:{b,f} olduğundan b veya f’den 1 durumunda gidilmesi gereken yerler alınmıyo mu yani D1->{b,f}:F olması gerekmez mi??Bu kısım da e’nin nasıl atandığını anlamadım şimdiden teşekkürler

  4. Şadi Evren ŞEKER Article Author

    evet haklısınız, D1 için doğrusu D kümesi yani {b,f} elemanlarından 1 ile gidilebilen kümeler olacak ki bu küme {b} elemanını içeren B kümesidir.

    Yani doğrusu D1->{b}:B olacak. Yazıdaki hatayı ilk fırsatta düzeltirim.

    Uyarınız için teşekkürler

  5. Magsud

    C1 (C kümesinden 1 değeri ile ulaşılabilecek olan durumlar): {e} : F (bu kümeye F ismini verelim)

    C’den 1 değeriyle ulaşılan durum neresi anlamadın orayı? Grafta böyle bir geçiş gözükmüyor. Aynı şekilde E’den 0 değeriyle yapılan geçiş için de geçeril. Açıklarsanız sevinirim

  6. Ömer Faruk Kurular

    Çok saolun çok güzel anlatmışsınız.Bu konuyu hintliler hariç anlatan bulamamıştım onlarında ne dediklerini anlamıyorum zaten 😀

  7. Emrah

    Hocam elinize sağlık. Sizden bir pumping lemma videousu da bekliyoruz, internette düzgün ingilizcesi bile yok, hepsi indian-english ve hiç bir şey anlaşılmıyor. Size güveniyoruz:) Şimdiden teşekkürler:)

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir