Biçimsel Diller ve Otomatalar (Sonlu Otomatalar)

Önceki yazımızda dil kavramını incelemiştik.

Deterministik sonlu durum makinesi, non-determinisitik sonlu durum makinesinin özel bir şeklidir. NFA’dan farklı olarak, ε geçişi yoktur. Bir durumdan bir geçiş sembolüyle en fazla bir tane duruma gidilebilir.

Deterministik sonlu durum makinesinin özelliklerini kısaca özetleyelim.

  1. Her durumdan (State) gidilecek koşulun tek bir durum göstermesi. Yani bir durumda başka duruma geçerken bir kelime ile sadece bir duruma gidilebilmesi.
  2. Herhangi bir girdi için, tek bitiş durumunun (final state) kabul edilmesi. (Birden fazla bitiş durumunun aynı anda kabul edilmemesi)

Adımlar iki kere yuvarlak içine alınıyorsa bu adım final state kabul ediliyor. Yani o adıma gelindiğinde makine diziyi kabul etmiş oluyor.

Örnek 1:

Tüm 0’ları ve 1’leri kabul eden otomatayı çiziniz.

Çözüm 1:

dfa

Örnek 2:

Sadece 1 ile biten dizileri kabul eden otomatayı çiziniz.

Çözüm 2:

dfa

Örnek 3:

Σ = {0,1} olan, çift sayıdaki uzunlukları kabul eden otomatayı çiziniz.

Çözüm 3:

 

dfa

Öncelikle 2,4,6 ve daha çok olan çift sayıdaki uzunlukları kabul eden otomata çizmemiz gerekiyor. 0 ve 1 kullanmamız önemli değil, bu yüzden ikisini de kullanabiliyoruz.

Örnek 4:

001 substringini kabul eden otomatayı çiziniz.

Çözüm 4:

001 substringini kabul eden dfa

 

Tahsin ALTINTAŞ

Computer science 4 life mottosuyla yola çıkmış bir bilgisayar mühendisi.

Bir cevap yazın

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