Esasen iki tür sonlu otomata (finite automaton) bulunmakta : belirli (deterministic) ve belirli olmayan (non-deterministic) sonlu otomata. İlkini açıklamaya çalışayım :
Bir belirli sonlu otomata $M$ 5 bileşenden oluşuyor
(i) : sonlu bir hal kümesi $Q$
(ii) : sonlu bir alfabe $\Sigma$
(iii) : bir $\delta : Q\times\Sigma\rightarrow Q$ fonksiyonu
(iv) : bir başlangıç hali : $q_0\in Q$
(v) : ve bir final halleri kümesi $F\subseteq Q$
ve şu şekilde çalışıyor :
$M$'e bir kelime $w$ verilir. Burada kelime alfabenin elemanları kullanılarak yazılmış sonlu bir dizidir. Yani $w=(l_1,...,l_n)$ ve $l_i\in\Sigma$. Daha sonra adım adım $\delta$ fonksiyonu kullanılarak yeni haller üretilir, yani adım adım $q_i=\delta(q_{i-1},l_i)\in Q$ elemanları hesaplanır. Eğer sonunda ulaştığımız hal, $q_n$, final hallerinden biriyse, yani $q_n\in F$ ise, $w$ kelimesi $M$ tarafından kabul edilir denir.
$W$ kümesi $\Sigma$ alfabesi kullanılarak yazılabilecek olan tüm kelimeler olsun (boş kelime de dahil olmak üzere). $L$ kümesi de $M$ belirli sonlu otomatasının kabul ettiği tüm kelimeler olsun. Bu $L$ kümesi $W$ kümesinin bir altkümesi. $L$ boş olabilir, tüm $W$ olabilir, çok ilginç başka şeyler de olabilir. $L$ kümesine $M$'in düzenli dili deniyor (regular language).
Arka plandaki fikir şu :
$M$ ilkel bir makineyi temsil ediyor. Makinenin üzerinde sadece yelkovanı olan bir saat var. Başlangıçta yelkovan belirli bir sayıyı göstersin (saatin gösterebildiği sayılar $Q$ ile ve yelkovanın başlangıçta gösterdiği sayı $q_0$ ile temsil ediliyor). Bu makineye ard arda birtakım girdiler veriyorsunuz, tabii ki bu girdiler makinenin anlamaya programlandığı girdiler olmak zorunda (bu girdiler $\Sigma$ alfabesi ile temsil ediliyor). Makine de verilen girdiye bakıp yelkovanın gösterdiği sayıyı değiştiriyor (makinenin girdi alıp yelkovanın konumunu değiştirmesi $\delta$ fonksiyonu ile temsil ediliyor). Bütün bu işlemin sonunda yelkovan belirli bir sayıyı gösteriyor olacak. Eğer bu sayı önceden belirlediğimiz güzel sayılardan ($F$ kümesinin elemanları) biri ise, bu girdi $M$ makinesi için anlamlı bir girdi. Eğer değilse, makinenize girdiğiniz girdi makineniz için anlamsız, saçma bir girdi. Hesap makinesine $elma+armut$ işlemini girmek gibi.
Şimdi öyle bir belirli sonlu otomata tasarlayalım ki $0$ ve $1$'lerden oluşan bir dizi verildiğinde bu dizide $0$'ın olmadığını kontrol etsin. Yani örneğin makinemiz $11111111$ dizisi verildiğinde bu dizide $0$ olmadığını anlasın (düzenli diller terminolojisini kullanırsak şu manaya geliyor : $M$'in düzenli dili, içinde en az bir kere $0$ içeren ikili diziler) :
(i) Önce alfabemizi belirleyelim. Verilen dizi $0$ ve $1$'lerden oluştuğuna göre, cevap belli : $\Sigma=\{0,1\}$.
(ii) $Q$ haller dizisini pek çok farklı şekilde seçebiliriz. En basit olanı şu $Q=\{e,h\}$. Bu harfleri evet ve hayır kelimelerinin baş harfleri olsun diye seçtim.
(iii) Başlangıç hali $q_0=h$ olsun. Yani makinemiz dizide $0$ olmadığı varsayımıyla ile başlayacak.
(iv) Final halleri kümesi $F=\{e\}$ olsun. Yani makinemiz sadece sonunda $e$ haline vardığı kelimeleri kabul edecek.
(v) Şimdi de makinenin asıl kısmı olan $\delta$ fonksiyonunu yazalım :
$Q\times\Sigma$ kümesi şu : $\{(e,0),(e,1),(h,0),(h,1)\}$. Fonksiyonu şöyle tanımlayalım :
$\delta(e,0)=e$
$\delta(e,1)=e$
$\delta(h,0)=e$
$\delta(h,1)=h$.
Makinemiz tamamlandı. Şimdi çalışıp çalışmadığına bakalım. Bunun için $\delta$ fonksiyonunu incelememiz lazım. Eğer makine $e$ haline bir kere girdiyse (ki amacımızı hatırlarsak, bu dizinin $0$ içermesi manasına geliyor), bir daha $e$ halinden çıkmıyor çünkü $\delta(e,0)=\delta(e,1)=e$. Ki bu da mantıklı, çünkü makine verilen dizide bir kere $0$ görmüşse, artık bu dizide $0$ var demektir, dizinin devamında ne olursa olsun $e$ hali $e$ hali olarak kalacaktır. Fakat başlangıç halimiz $h$. Hangi durumda $h$ halinden $e$ haline geçiyoruz? Hatırlayalım : $\delta(h,0)=e$. Yani makine $0$'ı gördüğü zaman $h$ halinde ise $e$ haline geçiyor. Ki bu da makinenin amacına uygun. Henüz $0$ görmediyse makine, $h$ durumunda bekliyor ve $0$'ı görünce de $e$ durumuna geçiyor.
Bir örnekte deneyelim, dizimiz $111001$ olsun :
1. Adım : $111001$
Makine başlangıç hali olan $h$ halinde.
2. Adım : $11001$
$1$ sayısını okuduk. $\delta(h,1)=h$ olduğu için, makine hala $h$ halinde bekliyor.
3. Adım : $1001$
İkinci $1$ sayısını okuduk. Makine hala $h$ halinde.
4. Adım : $001$
Üçüncü $1$ sayısını okuduk. Makine hala $h$ halinde.
5. Adım : $01$
$0$ sayısını okuduk. Makine $h$ halindeydi. Yeni halimiz $\delta(h,0)=e$. Bundan sonra hep $e$ halinde kalacak.
6. Adım : $1$
Makine $e$ halinde.
7. Adım :
Makine $e$ halinde.
Final halleri kümemiz $\{e\}$ olduğu için ve en son gördüğümüz hal $e$ olduğu için $111001$ dizisi makinemiz tarafından kabul ediliyor.
Peki belirli sonlu otomataların önemi nedir, bilgisayarlarla ilişkisi nedir? Belirli sonlu otomatalar daha önceden de dediğim gibi ilkel makineleri temsil ediyor. Önemleri ise sınırlı bir işlem gücü ile çözülebilecek birtakım problemleri temsil ediyor olmaları. Açıklamaya çalışacağım. Çok önemli bir soru şu : verilen bir sonlu alfabe $\Sigma$ ve $\Sigma$ kümesi kullanılarak yazılabilecek bütün sonlu kelimelerin kümesi $W$'yu düşünelim. $P(W)$ ise $W$ kümesinin kuvvet kümesini belirtiyor olsun. Acaba $P(W)$ kümesinin hangi elemanları bir belirli sonlu otomatanın düzenli dilidir? Örneğin $\Sigma=\{0,1\}$ için içinde $0$ içeren sonlu diziler kümesinin üstteki belirli sonlu otomatanın düzenli dili olduğunu biliyoruz. Acaba hangi tipteki kümeler düzenli dil olabilir? Bir teorem : $L=\{\emptyset,01,0011,000111,00001111,...\}$ kümesi hiçbir sonlu otomatanın düzenli dili olamaz. Kanıtını burada vermeyeceğim fakat içgüdüsel olarak sebebi, bu kümeyi tanıması için ilkel bir makinenin sonsuz hafızaya sahip olması gerekmesi. Tabii ki modern bilgisayarlarda herhangi bir programlama dili kullanarak bu dili tanıyacak bir algoritma kolaylıkla yazabilirsiniz. Bunun sebebi de bilgisayarları temsil eden kavramın belirli sonlu otomatalar değil, Turing makineleri olması.
Not : İngilizceden Türkçeye yapılan çeviriler bana aittir, Türkçedeki doğru kavramlar olup olmadığından hiç emin değilim.