- Desenleri tanımak için sonlu otomatlar kullanılır.
- Giriş olarak sembol dizisini alır ve durumunu buna göre değiştirir. İstenilen sembol bulunduğunda geçiş gerçekleşir.
- Geçiş sırasında otomatlar ya bir sonraki duruma geçebilir ya da aynı durumda kalabilir.
- Sonlu otomatların iki durumu vardır, Durumu kabul et veya Reddetme durumu . Giriş dizesi başarılı bir şekilde işlendiğinde ve otomatlar son durumuna ulaştığında kabul edecektir.
FA'nın Resmi Tanımı
Sonlu bir otomat, 5'li gruplardan (Q, ∑, δ, q0, F) oluşan bir koleksiyondur; burada:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Sonlu Otomata Modeli:
Sonlu otomatlar, giriş bandı ve sonlu kontrol ile temsil edilebilir.
Giriş bandı: Belirli sayıda hücreye sahip doğrusal bir banttır. Her giriş sembolü her hücreye yerleştirilir.
Sonlu kontrol: Sonlu kontrol, giriş bandından belirli bir giriş alındığında bir sonraki duruma karar verir. Bant okuyucu hücreleri soldan sağa doğru tek tek okur ve aynı anda yalnızca bir giriş sembolü okunur.
Otomata Türleri:
İki tür sonlu otomat vardır:
- DFA(deterministik sonlu otomat)
- NFA(deterministik olmayan sonlu otomatlar)
1. DFA
DFA, deterministik sonlu otomatları ifade eder. Deterministik, hesaplamanın benzersizliğini ifade eder. DFA'da makine yalnızca belirli bir giriş karakteri için tek bir duruma gider. DFA, boş taşıma işlemini kabul etmez.
2. NFA
NFA, deterministik olmayan sonlu otomata anlamına gelir. Belirli bir giriş için herhangi bir sayıda durumu iletmek için kullanılır. Boş hareketi kabul edebilir.
DFA ve NFA ile ilgili bazı önemli noktalar:
- Her DFA, NFA'dır ancak NFA, DFA değildir.
- Hem NFA hem de DFA'da birden fazla son durum olabilir.
- DFA, Derleyicide Sözcüksel Analizde kullanılır.
- NFA daha çok teorik bir kavramdır.