Sonlu Durum Makinesi Nedir? Konu Anlatımı ve Örnekleri
Finite State Machines, "FSM"
Sonlu durum makinesi (FSM), mantığı modellemek için kullanılan soyut bir hesaplama modelidir. Bir dil, yalnızca ve ancak bir FSM tarafından tanınabiliyorsa normal kabul edilir.
Sonlu Durum Makinesi Konu Anlatımı
Düzenli diller, hesaplama teorisinde önemli bir konudur. Bilgisayar biliminde normal bir dil, bir dizi diziden oluşan resmi bir dildir. Bu diziler, tanımlanmış bir alfabedeki sembollerden oluşur.
Sonlu Durum Makinesi Tasarımı ve Örnekleri
İşte {0,1} olan bir alfabe. Küme, dili oluşturan dizelerin 0’lar ve 1’lerden oluşması gerektiğini ve başka hiçbir sembol içermemesi gerektiğini gösterir.
Sembollerin nasıl birleştirilebileceğini göstermek için bir dizi kurala da ihtiyaç vardır. Bu kurallar, bir sonlu durum makinesi veya düzenli bir ifade kullanılarak ifade edilebilir.
Sonlu durum makineleri genellikle, FSM’yi görselleştirmenin yararlı bir yolu olan durum geçiş diyagramları olarak çizilir.
Basit bir robot düşünün. Sonlu sayıda durum içinde var olan robotu düşünün. Bunların ayrık olması gerekir (yani durumlar eşzamanlı veya örtüşemez).
Robot açılabilir (on) veya kapatılabilir (off). Aynı anda hem açık hem de kapalı olamaz. Her duruma bir sayı vermek gelenekseldir: S0, S1, vb. Bu sayılar, destekleyici diyagramları daha az karmaşık hale getirir ve yorumlamayı kolaylaştırır.
Robotun durumları değiştirebilmesi için bir girdiye ihtiyaç vardır. Bu bir geçişe neden olur: devletler arasında bir hareket. Aynı giriş, giriş algılandığında makinenin durumuna bağlı olarak farklı bir etkiye sahip olabilir.
Örneğin, robotun tek bir açma/kapama düğmesi olabilir. Robot kapalı durumdayken düğmeye basarsanız açılacaktır (ya da ‘açık durumuna geçiş’ diyebiliriz). Robot açık durumdayken butona basarsanız kapalı durumuna geçecektir.
En basit robotların bile birçok durumu olması muhtemeldir. Şimdilik, aşağıdaki gibi numaralandırılan ve açıklanan üç durumu göz önünde bulundurun:
| Durum | Açıklama |
|---|---|
| S0 | Switched off (Kapalı) |
| S1 | On and moving forward (Açık ve ilerleme) |
| S2 | On and moving backward (Açık ve geriye doğru hareket) |
Ayrıca iki girdiyi de ele alalım:
| Giriş | Açıklama |
|---|---|
| Button push | Açma/Kapama düğmesi |
| Sensor | Çarpışma sensörü |
Artık robotu bir sonlu durum makinesi olarak modellemek için bir durum geçiş diyagramı çizmek mümkündür.
Her geçişin, durumlar arasındaki hareketi tetikleyen girdiyle etiketlendiği şöyle gözlemlenebilir:
Kaynak: https://isaaccomputerscience.org/concepts/dsa_toc_fsm
