Tip 3 Düzenli Diller (Regular Grammars), Chomsky Hiyerarşisi (Chomsky Hierarchy)‘nin en alt seviyesidir. Dilbilgisinin en kısıtlı biçimidir. Bu diller, bir Finite State Machine (Sonlu Durum Otomatı) tarafından kabul edilebilen tüm dillerdir. Tip 3 dillerde mutlaka bir sonlu durum gerekir. Hafıza yoktur ve belirli bir bellek barındırmaz.
Finite State Machine (Sonlu Durum Otomatı), sınırlı sayıda durumdan, durumlar arası geçişlerden ve eylemlerin birleşmesiyle oluşan davranışların bir modelidir.
Sonlu durum otomatları, çıktı üretenler ve çıktı üretmeyenler olarak ikiye ayrılır. Çıktı üretmeyenler deterministik ve determinist olmayan olarak ikiye ayrılır.
Çıktı üretenler; Moore ve Mealy makineleridir. Moore Makinesi state’ten çıktığı anda yazma işlemi yapıyor. Mealy Makinesi geçiş gerçekleştirirken yazma işlemi yapıyor.
Otomatlar, biçimsel diller teorisi kapsamında bilgisayarların soyut birer modelidir. Eğer otomatın çıktı olarak yanıtı sadece “evet” veya “hayır” ise, bu makine çıktı içermeyen sonlu durum otomatı olarak adlandırılır. Sonlu durum otomatları, sonlu sayıda durum ile sonsuz sayıda giriş dizgisini kontrol edebilir.
Otomat Kuramı Nedir? Finite Automata Nedir?
Otomat (automata) kelimesi, otomasyon kelimesiyle yakın anlamda olup belirli bir süreçlerin gerçekleştirimini sağlayan otomatikleştirilmiş işlemler bütününü ifade eder. Otomat kuramı ise, otomat olarak adlandırılan basit makineler üzerinden gerçekleştirilen hesaplama işlemlerinin mantığıyla ilgilenir.
Temelleri 20.yy’da matematikçilerin insanın belirli özelliklerini taklit edebilen, özellikle de hesaplamaları daha güvenilir, hızlı biçimde yapabilen ve hem kuramsal hem de uygulamaya dökülmüş makineleri geliştirmeye başlaması ile atılmıştır.
Otomatlar sayesinde bilgisayar bilimciler makinelerin fonksiyonları nasıl hesaplayabildiği ve problemleri nasıl çözebildiğini anlama imkanı bulur. Daha da önemlisi, bir fonksiyonun hesaplanabilir (computable) olarak tanımlanması veya bir sorunun karar verilebilir (decidable) olup olmadığının anlaşılması bu kuram ile mümkündür.
Tip 3 dillerde mutlaka sonlu durum gerekir. Hafıza yoktur, belirli bir bellek barındırmaz.
Finite State Machine (Sonlu Durum Otomatı);
- Girdi şeridi olarak da bilinen sonlu bir bellek,
- Okuyucu başlık,
- Sonlu sayıda ve boş olmayan durumlar,
- Bir giriş alfabesi,
- Durumlar arası geçişleri betimleyen bir geçiş fonksiyonu,
- Bir başlangıç durumu,
- Sonlu sayıda durma durumundan oluşan soyut bir hesaplama aygıtıdır.
Çalışma Mantığı
Girdi şeridi hücrelere bölünmüştür ve her bir hücre giriş alfabesine ait bir sembol barındırır. Okuyucu başlık, bir adımda şeritten tek bir sembolü okur. Geçiş fonksiyonu üzerinden bir sonraki durum belirlenir. Okuyucu başlık soldan veya sağdan başlayarak okuma yapabilir. Okuyucu başlık şerit üzerinde yazma işlemi yapamaz ve geriye doğru gidemez. Dolayısıyla bir sonlu durum otomatı o anda okumakta olduğu sembolden önceki sembolleri hatırlayamaz. Bu durum sonlu durum otomatının en önemli kısıtıdır.
Biçimsel Tanım
Bir sonlu durum otomatı Q, Σ, δ, q0, F şeklinde bir beşli olarak tanımlanır ve bu tanıma göre;
Q: sonlu sayıda elemana sahip bir durumlar kümesi
Σ: sonlu sayıda elemana sahip semboller kümesi (alfabe)
δ: geçiş fonksiyonu
q0: herhangi bir girdinin işlenmeye başlayacağı başlangıç durumu
F: Q içindeki son durum(lar) kümesi