Sonlu Durum Makineleri

Ön Söz

Merhabalar. Bu yazımda sonlu durum makineleri hakkında bir ön bilgi vererek kullanım alanları hakkında hem araştırma ve öğrenim bilgilerimi hem de  kendi fikirlerimi paylaşacağım.

Sonlu Durum Makineleri ve Kullanım Alanları

Sonlu Durum Makineleri uluslararası adı ile Finite State Automata olarak bilinmektedir. Sonlu Durum Makinelerinden bahsedebilmek için biraz yapılarından ve çalışma prensiplerinden bahsetmem gerekir. Bu sistemlerle günlük hayatımızda, fabrikalarda, ofisimizde karşılaşabiliriz. Hatta evlerimizde, aracımızda, kullandığımız telefon, saat her yerde karşılaşabiliriz. İnsanların işlerini kolaylaştırmak, rutin bir işi insansız olarak yapabilmek en yaygın kullanım alanları arasında sayılmaktadır denilebilir. Aslında bu sistemler ihtiyaçlara karşılık gelen çözümleri üreten her türlü otomatik iş sistemini ifade eden ve uygulayan robot sistemlerinin temel parçalarıdır.

Bir tetikleme ile etkileşime girerek, bir başlangıç durumundan seçime bağlı olarak bir durumdan, başka bir duruma geçişler yayabilen, nihayetinde son duruma ulaşabilen veya aynı zamanda çıkış üretebilen sistemlerdir. Sonlu Özdevinirler olarak da anılan bu sistemler genel olarak kendi arasında deterministik (DFA) ve none deterministik (NFA) şeklinde iki gruba ayrılıyor. Aslında bu iki kavram tamamı ile bir birinden ayrı sistemler değildir, NFA dediğimiz yapı DFA dediğimiz yapının sadeleştirilmiş halidir diye biliriz. Aynı işi yapabilen sistemin, sadeleştirilmesi yöntemi sonucunda NFA sistemler elde ediliyor. Amaç sistemin hem daha minyatür olması, daha az yer kaplamasına, hem de daha ekonomik olması, maliyetinin düşük olmasına sebep olmaktadır.

Günlük hayatımızda en fazla karşılaştığımız sonlu durum makineleri, her gün onlarca kez geçtiğimiz geçiş turnikeleri, kart ile geçiş yaptığımız kapılar, hatta otopark kapılarını en basit kullanım alanları olarak sayabiliriz. Çay, kahve yapan otomatlar, mini bir büfe olarak çalışabilen su, bisküvi, çikolata, sıcak simit ve benzeri ürün satabilen, pizza yapabilen otomatlar ofislerimizde, caddelerde sıklıkla karşılaştığımız gelişmiş finite state otomatalardır.

Fabrikalarda üretim bantlarında çalışan robotların bazıları da yine sonlu durum makinelerinin oldukça gelişmiş örnekleridir. Uçak yapımında, otomobil yapımında, şişeleme, paketleme, dolum gibi işleri yapabilen son durumlu makineler bulunmaktadır. Trafik ışıkları da bir sonlu durum makinesidir diyebiliriz.

Çay Kahve ve Yiyecek Otomatları:

Başlangıç tetiklemesi para atıldıktan sonra, insan etkileşimi için seçenekleri bekleme durumuna geçiş sağlanır. Seçilen giriş ile tanımlı durumda yapılması gereken işler tamamlanır ve müşteriye kahvesi çıkış bölümünden verilerek son duruma geçiş yapılır.

Oyun Makineleri:

Bir jeton, yada kart ile boş durumdan başlangıç durumuna geçiş yapar ve bu tetikleme ile oyuncunun etkileşimi için seçenek menüsünde bekler. Oyuncu seçtiği oyun şekline göre tanımlı süre boyunca oyun konsolunu kullanmaya devam eder. Süre sonunda oyuncuya kaldığı yerden devam etmesi için bir süre jeton atması beklenir. Jeton atılmaz ise oyun başlangıç konumuna geri döner ve konsolun kullanımı engellenir.

Araba Yıkma Makineleri:

Arabanızı yıkama noktasına yerleştirdikten sonra başlangıç butonuna basılır. Bu andan itibaren yağmurlama şeklinde ıslatma işlevi devreye girer belirli bir süre sonra yıkama fırçaları dönmeye başlar ve harekete geçer. Dikkat edilirse burada geçişler yeniden bir insan etkileşimi olmaksızın devam etmektedir. Burada verilen bir giriş ile lamda geçişi, more, mealy makineleri gibi yapılar kullanılmaktadır. Bu yapılar çıkış üreterek bu çıkışları giriş olarak kullanabilen sistemler olarak tasarlanmış makinelerdir. Örneğin aracın boyu, yüksekliği gibi kavramları bu makineler dışarıdan bir giriş alarak öğrenmemektedir. Yıkama fırçaları arabanın eteklerinden başlayarak yukarı doğru belirli aralıklarla ilerleme yönünde devam etmeye çalışmakta hafif bir engelleme anında ilerlemeyi keserek yükselmeye devam etmekte, belirli bir yükseklikten sonra tekrar ilerleme yönünde hareket etmekte ve nihayetinde bir engel ile karşılaşmaz ise bunu hafızaya almakta ve aracın bagaj yüksekliğini tespit etmektedir, bu eylem aracın ön tarafına ulaşana kadar devam etmekte ve geri dönüş işlemi için hafızasında bulunan dönüş koordinatları ile tekrar bu testleri yapmadan yıkamayı sonlandırmakta. Yine hiçbir etkileşim beklemeden yıkama sonunda ulaştığı durumdan örneğin bir lamda geçişi ile kurutma durumuna geçiş yapılmakta ve hafızadaki giriş verileri ile aynı koordinat boyunca aşağı yukarı hareketler ile araba kurutulmaya başlanmakta ve tamamlanmaktadır. Bu arada olası bir acil durumda işlemleri iptal edebilen stop butonu ile tüm bu işlemler iptal edilebilmektedir.

Trafik Lambaları:

Trafik lambaları da benzer şekilde bir kez başlatıldıktan, güç verildikten sonra durumlar arası geçişleri sürekli olarak tekrarlayan bir sonlu durum makinesidir denilebilir. Son durum başka bir durumu tetikleyerek süreklilik sağlanmaktadır.

Üretim hattında çalışan dolum, paketleme, şişeleme otomatları:

Örneğin bir şişeleme hattındaki FSM girişine uygulanan tetikleme ile gelen sıradaki şişeyi alarak kapak kapatan duruma getirir, bu duruma ulaştığında şişeyi bırakır ve yeniden başlangıç durumuna döner. Bu arada kapağı takan durum gelen şişeyi görme elemanı ile görüp tetiklen kapak takıcı durum, şişeye bir kapak vidaladıktan sonra başka bir kapağı alarak yeniden hazır konumda bekler, bir sonraki durum şişeyi alarak paketleme alanına bırakır. İşte bu şekilde aynı anda birkaç farklı işi yapabilen sistemlerin geliştirilmesi FSM tasarımları VHDL dili ile programlan donanımlar ile FPGA değimiz paralel işlemler yapabilen üretim hatları oluşturulmasında kullanılır. Bu hatlar tıpkı insanlar gibi aynı anda gazete okuyup, kahvaltı yaparken, çayını yudumlamak gibi çalışırken, başka bir iş için örneğin banyo yapma durumuna geçtiğinizde yeniden programlanıp, bir taraftan su döküp yıkanırken, diğer taraftan vücudunuzu sabunlama işini de aynı anda yapmaya başlamak gibi düşünülebilir.

Elektronik Kol Saati Fonksiyonları:

Elektronik kol saatlerindeki fonksiyonları örnek alırsak FSM ile hayatımızın her alanında iç içe olduğumuza kanaat getirmemiz zor olmayacaktır. Kol saatimiz üzerindeki düğmelere basma sayısı, yada basarak bekleme süresini bir tetikleyici giriş olarak aldığını düşünürsek örneğin A düğmesine 1 kere kısa basınca tarih fonksiyonu 2 kere basınca kronometre fonksiyonu gibi geçişleri görebiliriz. Buradaki durum ve geçiş değişkenleri tamamen bizim tarafımızdan girilen girişe göre hareket etmektedir. Kronometre fonksiyonuna geçildiğinde B düğmesine 1 kez kısa basılarak kronometre çalıştırılır, bir kez daha basıldığında durdurulur, uzun süre basıldığında ise kronometre resetlenir gibi. Bir örnek FSM ye iyi bir örnek olabilir.

Bankamatik ATM (Automated Teller Machine)

Bu örnek hepimizin kullandığı Bankamatik Sisteminde FSM nin kullanımı yönetminden Davranış Durum Makinesi şu şekilde çalışıyor:

Başangıçta ATM kapalıdır.

Güç açıldıktan sonra ATM kendi kendini test etme işlevine gider.

Test başarısız olursa Out Of Service gider.

Test başarılı olursa müşteri etkileşimi olana kadar boşta bekler.

Boşta bekleyen ATM ye müşteri kartını yerleştirdiği anda durum tetikleyici devreye girer ve müşteri kartını okuma işlemini başlatır.

Bu esnada oluşan müşteri herhangi bir anda iptal tuşuna basar ise kart tekrar iade edilir.

Okuma işlemi devamında müşteri bilgilerinin doğrulanması için müşterinin veri girişi beklenir.

Müşteri bilgileri doğrulandığında müşteri şlemleri seçenekleri menüsüne geçilir ve etkileşim için beklenir.

Müşteri işlemini seçer ise başka bir duruma geçiş yapılır ve buna benzer durumlar arası geçişler müşterinin işlemini sonlandırana kadar devam eder.

Bilgisayar Programları

Belirli sayıdaki durumlar arasında geçiş yapabilen veya çıkış üretebilen sistemler FSM olarak tanımlandığına göre bilgisayar programının da sürekli aynı durum için aynı işler üreten FSM dir denilebilir. Bilgisayar programlama dillerinde özellikle donanımsal programlama dillerinde FSM kullanılmaktadır. Örneğin VHDL (HDL) dediğimiz donanımsal programlama dilinde donanımın giriş ve çıkış sinyalleri FSM ler ile tasarlanarak kontrol edilir. Örneğin bir Saat darbesi işi yapan FSM düşünüldüğünde bu işi yapan mantık elemanı devreler Moore Makinesi veya Mealy Makinesi olarak dizayn edilebilirler. FSM makineleri durum makinelerinin giriş alfabesi tanıyan sistemler olduğunu Moore ve Mealy makinelerinin de çıkış üreten FSM ler olduğunu biliyoruz.

Yaşayan ve sürekli gelişen bir sonlu durum makinesi

Ağlayan Bebekten FSM Olurmu

Okuduğum İngilizce bloglardan birinde blog yazarı “Bebeğim bir sonlu durum makinesi” yazmış. Elini kapıya sıkıştırınca ağlamaya başlayan bebeğini ne yaptılarsa susturamamışlar. Bebeğin annesi onu yatağına bıraktıktan sonra tekrar kucağına aldığında ise bebek susmuş. Düşündüğünde tesadüfen uyguladıkları bu olay gerçekten de FSM davranışı. Bilinmeyen veya tanımlanmayan bir giriş aldığında son duruma geçemeyen sistem olarak düşünürsek, yatağında ağlarken, kucağa aldığında susan bebeğin tanıdığı bir giriş alfabesidir. Tanınan bilinen bir durum olan yatakta olma durumu giriş başlangıç olarak ağlamanın başlaması, kucağa alınma geçişi ile kucaktaki durumda son bularak susması son durum eylemi çok ilginç bir FSM örneği olabilir. Gerçekten de araştırdığımda bebek gelişimi uzmanları bu yöntemi kullandıklarını ve başarılı sonuçlar aldıklarını belirtmekteler. Örnekteki bebek en temel geçiş turnikesine eş değer bir FSM dir.

Sonuç

Sonlu Durum Makineleri günümüz teknolojisinde kullanılan her elektronik devrede ve bilgisayar alanda kullanılan uygulamalarda temel donanım parçası olarak kullanılır demek yanlış olmayacaktır. Daha gelişmiş sistemlerin oluşturulması için FSM ler oluşturularak örneğin bilgisayarların, yazmaçlarının oluşturulması, giriş çıkış birimlerinin oluşturulması, kontrol birimlerinin oluşturulması, programlanabilir anahtarlama devrelerinin oluşturulması temeli düşünülürse gelişmiş her türlü otomatın temel yapı taşıdır dememiz gereken yapılardır. FPGA denilen sistemleri FSM lerin paralel kullanımının sağlanması olarak basitçe ifade edilirse, bebeğin büyüyüp insan gibi davranması örneğin de FSM ve FPGA ilişkisini açıklamamıza yardımcı olabilir.

Konuyu merak edenler için yapmış olduğum bu çalışma umarım giriş seviyesinde yardımcı  bir kaynak olacaktır.

Serkan UĞUR