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:

Örnek 2:

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

Çözüm 2:

Örnek 3:

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

Çözüm 3:

Ö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: