Tam Otomat

Sonlu otomatın temel tanımında her durumdan her sembol için bir geçişin bulunması şart değildir. Tam otomat, her durumdan giriş alfabesinin her sembolü için geçişi tanımlı olan otomattır.

Tam Otomat Nasıl Kurulur?

Şu A = ⟨Q, Σ, δ, q₀, F⟩ otomatını ele alalım:

Burada q₀ durumundan “b” harfi için çizilmiş bir geçiş yok. Böyle bir durumda otomatın verilen giriş sözcüğünü kabul etmediğini söyleriz. Ancak biçimselleştirme açısından geçiş fonksiyonu δ’nın bazı değerler için tanımsız olması uygun olmayabilir; burada örneğin δ(q₀, b) tanımlı değildir.

Bunu kolayca çözebiliriz: bir fazla durumu olan denk bir otomat kurarız. “Eksik” geçişler bu duruma gider, bu durum kabul durumu değildir ve sonraki tüm girişler bu durumda döngüde kalır. Bu otomata tam otomat diyoruz. Düzenlenmiş denk otomat şöyle görünebilir:

q_hata durumunu ekledik. Diğer durumlardan bu duruma, yalnızca daha önce orada geçiş yoksa geçiş çizdik. Bu durum kabul durumu değildir ve sonraki tüm girişler için kendi üzerinde döner. Önceki otomatta eksik bir geçişle karşılaştığımız yerde burada eksik geçiş yoktur; otomat q_hata durumuna düşer.

Bu yüzden genelliği bozmadan, otomatın durumlar ile alfabedeki sembollerin tüm kombinasyonları için geçişlerinin tanımlı olduğunu her zaman varsayabiliriz.

Tanım

A = ⟨Q, Σ, δ, q₀, F⟩ tam otomatı için şu geçerlidir:

$$\mathrm{\forall }q\in Q\mathrm{\forall }a\in \mathrm{\Sigma }\mathrm{\exists }r\in Q:\delta (q,a)=r.$$