Sonlu Ototmatlar (Finite Automaton)

Yazan: Şadi Evren ŞEKER

Bir sonlu durum makinesinin formal şekilde gösterilmiş halidir. Buna göre bir otomat’ı oluşturan 5 farklı unsur bulunur. Bunlar o otomatta  bulunan durumlar (states) o otomatın durumları arası geçişlerin alabileceği semboller kümesi olan alfabe, o otomattaki durumlar ve alfabeler arasındaki geçişi gösteren fonksiyon (transition function) ve son olarak otomattaki bitiş durumlarını gösteren küme (set of accept sets) olarak sıralanabilir.

Bir sonlu otomat aşağdaki şekilde gösterilebilir:

(Q,Σ,δ,q₀,F)

Q: durumlar kümesidir (states)

Σ: dilin tanımlı olduğu semboller kümesi (alfabe)

δ: geçiş fonksiyonu Q x Σ → Q

q₀ ∈ Q , Q kümesinin bir elemanıdır ve başlangış durumunu (state) gösterir

F ⊆ Q , Q kümesinin bir alt kümesi olan F kümesi, otomatın kabul ettiği bitiş durumlarını gösterir.

Örneğin aşağıda verilmiş olan sonlu durum makinesini sonlu otomat şeklinde yazalım:

Q: { q1,q2,q3 }

Σ: {0,1}

δ:

0

1

q₁ başlangıç durumudur.

F = { q₂ }

olarak atanır.