Sonlu Otomat

Sonlu otomat (İngilizce finite state machine ya da finite automaton), birkaç durumdan ve birkaç geçişten oluşan, kendisine verilen sözcüğü kabul edebilen ya da reddedebilen ilkel bir bilgisayarın hesaplama modelidir.

Örnek

Sonlu otomatı önce resmî olmayan biçimde, onu betimleyen bir durum diyagramı yardımıyla anlatalım:

Otomat durumlardan oluşur; şekilde q₀, q₁ ve q₂ olmak üzere üç yuvarlak durum var. Bu durumlar arasında geçişler vardır; bunlar oklardır. Otomatta ayrıca bir başlangıç durumu olmalıdır; burada bu, q₀ durumudur. Başlangıç durumu genellikle, hiçbir durumdan çıkmayıp ona yönelen bir okla gösterilir. Otomatta ayrıca genellikle bir kabul durumu bulunur; bunu çift çizgiyle gösteririz, şekilde bu q₂ durumudur.

Böyle kurulmuş otomat bazı sözcükleri kabul eder. Otomata sözcükler veririz ve otomat bu sözcükleri kabul etmeyi dener. Kabul ederse otomat EVET, etmezse HAYIR yanıtını verir. Örnek otomatımız “a, b, c” harflerinden oluşan sözcükleri kabul etmeyi dener; o hâlde “abbc” sözcüğünü deneyebiliriz.

Başlangıç durumu q₀’da başlarız ve girişte “abbc” sözcüğü vardır. Bundan sonra oklara göre ilerleriz.

Sözcüğü her zamanki gibi soldan sağa okuruz; yani ilk olarak “a” sembolünü alırız. “a” girişi için ok q₁ durumuna gider, biz de oraya geçeriz ve “a” sembolünü sözcükten sileriz. Girişte “bbc” sözcüğü kalır:

“b” girişi için ok yine q₁ düğümüne geri döner. İlk harfi yine sileriz ve girişte “bc” sözcüğü kalır. Yine q₁ durumunda kalırız. Sonunda girişte “c” sözcüğü kalır. q₁ durumundan “c” girişi için giden ok bizi q₂ durumuna götürür.

Giriş sözcüğündeki tüm harfleri tükettik ve kabul durumu olan q₂ durumundayız. Demek ki bu sonlu otomat “abbc” sözcüğünü kabul eder.

Sonunda kabul durumunda olmasaydık, otomat sözcüğü kabul etmezdi. Aynı şekilde, herhangi bir durumda gidecek yer bulamasaydık da otomat sözcüğü kabul etmezdi. Örneğin “ab” girişi için q₁ durumuna gelir ve orada kalırdık — otomat böyle bir sözcüğü kabul etmez. “aabbc” sözcüğünü denersek yine şansımız yaver gitmez, çünkü q₁ durumundan “a” harfi için giden bir ok yoktur.

Sonlu otomat böylece belirli bir sözcük kümesini tanımaya yarar. Uygulamada otomatı örneğin verilen giriş sözcüğünün geçerli bir e-posta olup olmadığını anlamak için kullanabilirdik.

Sonlu Otomatın Tanımı

Sonlu otomatın ne olduğuna dair önceki sezgisel fikri biçimlendirmemiz gerekir; ancak o zaman otomatlarla daha iyi çalışabiliriz.

Sonlu (deterministik) otomat, şu özelliklere sahip bir ⟨Q, Σ, δ, q₀, F⟩ beşlisidir:

• Q sonlu bir durumlar kümesidir,
• Σ (büyük sigma) alfabedir (sonlu bir sembol/harf kümesi),
• δ: Q × Σ ⟶ Q geçiş fonksiyonudur,
• q₀ ∈ Q başlangıç durumudur,
• F ⊆ Q kabul (son) durumları kümesidir.

Önceki otomata dönersek,

Q durumlar kümesinde üç durum olduğunu söyleyebiliriz: Q = {q₀, q₁, q₂}. Σ alfabesi, otomatın kabul edeceği ya da reddedeceği sözcükleri kurabileceğimiz harfleri içerir. Burada büyük olasılıkla Σ= {a, b, c} alfabesidir, ama herhangi bir üst küme de olabilir. Başlangıç durumu q₀, yine q₀ durumudur; bu konuda bir değişiklik yok. Bu otomatta kabul durumları kümesinde yalnızca bir durum vardır: F = {q₂}.

Geçiş fonksiyonu ise harfli o üç oktur. δ: Q × Σ ⟶ Q gösterimi kafanı karıştırıyorsa, bunun yalnızca δ fonksiyonunun (fonksiyon, belki daha doğrusu eşleme) iki parametre aldığı anlamına geldiğini bil: Q kümesinden bir durum ve Σ kümesinden bir harf. Fonksiyon çağrıldığında yeni bir durum döndürür. Geçiş fonksiyonumuzu bir tabloyla şöyle tanımlayabiliriz:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

δ(q₁, c) çağrısını yaparsak üçüncü satırı uygularız ve fonksiyon q₂ durumunu verir — diyagramdaki gibi. q₁ durumundaysak ve girişte “c” harfi varsa q₂ durumuna geçeriz. Otomatın bir sözcüğü kabul etmesinin ne demek olduğunu biçimsel olarak tanımlamadan önce bu kavramın sezgisel anlayışından yararlanıp birkaç örnek daha görelim.

Diğer Örnekler

1. İkili alfabe üzerinde, yani Σ= {0, 1} için çalışan ve yalnızca 1 ile biten sözcükleri kabul eden bir otomat oluştur. Örneğin 1, 01, 000001, 0101011 sözcüklerini kabul etsin.

   

   Otomatımızın iki durumu var — başlangıç durumu q₀ ve kabul durumu q₁. Girişte 1 rakamı olduğunda kabul durumu q₁’e geçeriz ve orada kalırız. Girişte 0 rakamı olduğunda ise kabul etmeyen q₀ durumuna geçeriz ve orada da kalırız.

2. İkili alfabe üzerinde, yalnızca ilk harfi son harfinden farklı olan sözcükleri kabul eden bir otomat kur.

   

   Otomat daha ilk adımda iki “alt otomata” ayrılır. Sözcük sıfırla başlıyorsa otomat sol kısma girer ve orada kalır, birle başlıyorsa sağ kısma geçer. Sonrası bildiğimiz gibidir: sol kısımdaysak ve girişte 1 varsa kabul durumuna geçeriz ve orada kalırız. Girişte 0 varsa kabul durumu olmayan q₁ durumuna geçeriz.

   Önceki otomatlardan farklı olarak bu otomatın birden çok kabul durumu vardır, yani F = {q₃, q₄}.

3. İkili alfabe üzerinde, art arda iki sıfır içermeyen sözcükleri kabul eden bir otomat kur.

   

   Bu otomat iki nedenle ilginçtir. Birincisi, boş sözcüğü kabul etmesidir. Otomata boş sözcüğü vermeyi deneyebiliriz; başlangıç durumu aynı zamanda kabul durumuysa otomat onu kabul eder, bu otomatta da böyle olmuştur. Boş sözcük art arda iki sıfır içermeyen bir sözcük olduğu için bu doğru sonuçtur. İkinci ilginç nokta, bu otomatın tüm durumlarının kabul durumu olmasıdır. Otomatın bir sözcüğü kabul etmemesinin tek yolu, bulunduğu durumdan uygun bir geçişin çıkmamasıdır. Bu, 0 için geçişi olmayan q₁ durumunda olur, çünkü o zaman sözcük art arda iki sıfır içerirdi.

4. {-,+,.,0,1,…,9} alfabesi üzerinde, bir sayıyı temsil eden sözcükleri kabul eden bir otomat kur. Yani ya 2, 548, 98263 gibi tam sayılar, ya da 5584.48, 3.14 gibi ondalık sayılar (programlama dillerindeki gibi ondalık ayırıcı noktadır); her ikisinin de eksi işaretli negatif biçimleri -2, -548, -3.14 ve açıkça yazılmış artı işaretli biçimleri +2, +548, +3.14. Aynı zamanda 0.123 sayısını başındaki sıfır olmadan yalnızca .123 olarak yazabilmeliyiz, hem de her iki işaretle birlikte. On rakam için on geçiş yazmak yerine N sembolünü kullandığımız yardımcı bir gösterim getirelim.

   

5. İkili alfabe üzerinde, 0ⁿ1ⁿ biçimindeki sözcükleri kabul eden bir otomat kur; yani sözcüklerin başında belirli sayıda sıfır, ardından aynı sayıda bir bulunur. Bu tür sözcüklere örnekler: 0011, 00001111, 01.

   Böyle bir otomat kurulamaz, çünkü sıfırların sayısını hiçbir yerde “aklımızda tutamayız”. İkinci örnekteki gibi birkaç “alt otomat” oluşturmamız gerekirdi, ancak bu “alt otomatların” sayısının sonsuz olması gerekirdi, yani her n değeri için bir tane.

Otomatın Hesaplamasının Biçimlendirilmesi

Sonlu otomatın kendisini biçimsel olarak tanımladık. Şimdi böyle bir otomatın aslında ne yaptığını, yani otomatın hesaplamasını tanımlamamız gerekiyor.

Otomatın konfigürasyonu: ⟨q, w⟩ ∈ Q × Σ^∗ ikilisine otomatın konfigürasyonu diyelim; burada q otomatın o anda bulunduğu durum, w ise sözcüğün henüz okunmamış kısmıdır. Σ^∗, Σ alfabesinin Kleene kapanışını, yani Σ alfabesinin harflerinden kurulabilecek tüm sözcüklerin kümesini gösterir. Kapanışa boş sözcük de dâhildir ve onu ε ile gösteririz.

⟨Q, Σ, δ, q₀, F⟩ otomatı verilmişse ve w sözcüğünü kabul etmeye çalışıyorsak, otomat ⟨q₀, w⟩ başlangıç konfigürasyonundadır. Şu otomata dönersek

ve w = abbc sözcüğünü kabul etmek istersek, başlangıç konfigürasyonu ⟨q₀, abbc⟩ olur.

Hesaplama adımını, otomatın konfigürasyonları arasında, yani (Q × Σ^∗) × (Q × Σ^∗) kümeleri arasında bir ↦ bağıntısı olarak tanımlarız. w = w₀w₁… w_n, w sözcüğünün henüz okunmamış kısmı olsun. O zaman ⟨q₁, w₀w₁… w_n⟩ ve ⟨q₂, w₁… w_n⟩ ikililerinin ↦ bağıntısında olduğunu söyleriz ve bunu şöyle yazarız:

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

ancak ve ancak δ(q₁, w₀) = q₂ ise. Örneğimize dönersek başlangıç konfigürasyonu ⟨q₀, abbc⟩’dir. Diyagramdan “a” girişi için q₁ durumuna ilerleyebileceğimizi görüyoruz. O hâlde şunu yazabiliriz:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

çünkü δ(q₀, a) = q₁ geçerlidir. Böylece bir hesaplama adımı yapmış olduk — verilen giriş için (= sözcüğün henüz okunmamış kısmının ilk harfi) hangi duruma gitmemiz gerektiğine baktık, oraya geçtik ve okunmamış kısımdan ilk harfi sildik. Böylece yeni bir konfigürasyon elde ettik.

Hesaplama adımı bağıntısının yansımalı ve geçişli kapanışını ↦ ^∗ ile gösteririz. K₁ ↦ ^∗ K₂ yazarsak, burada K₁, K₂ otomatın konfigürasyonlarıdır, bu K₁ konfigürasyonundan birkaç hesaplama adımıyla K₂ konfigürasyonuna ulaşabileceğimiz anlamına gelir; yani şöyle sonlu bir konfigürasyon dizisi vardır:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

Örneğin bizim otomatımızda ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩ geçerlidir, çünkü iki hesaplama adımı yaparsak elimizde “bc” sözcüğü kalır ve q₁ durumunda kalırız. Yani şu konfigürasyon dizisi vardır:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

Otomat w sözcüğünü kabul eder, ancak ve ancak $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ olacak biçimde bir q_f ∈ F varsa. Bu, otomatın w sözcüğünü ancak ve ancak şöyle bir hesaplama adımları dizisi varsa kabul ettiği anlamına gelir: bu dizinin sonunda sözcüğün tamamını okumuş olmalıyız ve otomatın kabul durumunda bulunmalıyız. Sözcüğün tamamının okunmuş olması, konfigürasyonda sözcüğün yerinde boş sözcük olan ε bulunmasıyla ifade edilir. Otomatımız abbc sözcüğünü kabul eder, çünkü şu konfigürasyon dizisi vardır:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

ve q₂ durumu kabul durumudur, q₂ ∈ F.

Otomat tarafından kabul edilen dil, otomatın kabul ettiği tüm sözcüklerin kümesidir. A otomatının dilini L(A) ile gösteririz. Böylece L(A) ⊆ Σ^∗ geçerlidir ve

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }\mid A\text{ otomatı }w\text{ sözcüğünü kabul eder}\}$$

Düzenli dil, herhangi bir sonlu otomat tarafından kabul edilen dildir.

Aynı dili kabul eden iki sonlu otomat denktir. Yani A₁ ve A₂ otomatları, L(A₁) = L(A₂) ise denktir.

Kaynaklar

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools