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

Bant Teorisi ve İçinde Bulunduğumuz Durum İlişkisi

Yarı İletkenlerde Bant Teorisi konusundan bahsedeceğim. Hemen söyleyeyim konu hakkında bilimsel açıklamalarda bulunmaktan daha çok gündemle birlikte harman yaparak düşündüren bir benzerlik hakkında özettleme yapacağım. Bu arada elektronik dersi bant teorisi konusunu anlamak için tuhaf bir örnek olabilir. Kim bilir belki anlayamadığınız bu konuyu kısmen ben anlatmış olabilirim.

Elektronik konusunun en önemli bileşenleri yarı iletkenlerdir. Ancak yarı iletkenler normal şartlar altındaki sıcaklıkta tam bir yalıtkandırlar yani mobilite sıfırdır. Şimdi diyeceksiniz ki sırf birkaç artistik cümle kurmak için yazı mı yazdın?

Aslında bu konuyu ele alıp işlememin asıl sebebi biz millet olarak Yarı İletken bir milletiz de demek..
Şimdi düşünüyorum da yarı iletkenler, iletkenliğe geçip işe yaramaya başlamaları için ya ısı etkisi ile yapılarındaki o düzgün kovalent bağlar kırılacak ve serbest elektronlar ortaya çıkacak ve harekete geçerek iletkenliği sağlayacaklar, yada dışarıdan enjekte edilen katkı atomun sebep olacağı yeni bağlardan arta kalacak serbest elektronlar veya deşik dediğimiz elektron boşlukları ile iletkenlik yapısına geçecekler.

Millet olarak kovalent bağlarımız kırılmasın diye çok çabalıyorlar çok... Böyle iyi hepimiz yalıtkanız, az ısımızı artıracak bir olay olsa hemen yeni gündem ile ateşimiz iniyor :) Eeee ozaman tek çare dışarıdan bir enjeksiyonla ya 5. gruptan bir verici atomun katkısıyla yeni bağlar kuracağız ve İletim Bandına geçeceğiz yada 3 gruptan bir alıcı atomla bağ kurup Valans Bandına geçeceğiz. Vallahi ben 20 yıldır Yasak Enerji aralığında öylece kalakaldım ne ısınıyorum ne soğuyorum nede dışardan kimsenin katkısı var.

5. grup, 3. grupta neyin nesi, ister siyasi düşünce deyin isterseniz sizi harekete geçirecek bir topluluk ama bugünlerde hakkaten dışardan bir etki ile hareket geçme vaktimin geldiğine inancım bas baya arttı. Ya 5. gruptan katkı alıp N Tipi yarı iletken olacağım yada 3. gruptan katkı alıp P Tipi yarı iletken olacağım farket mez sonuçta kesinlikle harekete geçeceğim.

Sanırım Fermi Enerji seviyemide  bir akım bulmadığım için olabilir.

Modern fiziğe göre bir atomdaki elektronlar en düşük enerji seviyeden başlayarak PAULI seçim ilkesine göre üst enerji seviyelerine yerleşirler öyleki bu yerleşmenin sonucunda yerleşecek atom kalmayınca daha üst enerji seviyeleri boş kalırlar. İşte aşağıda elektronlar tarafından doldurulan enerji seviyeleinden sonraki ilk seviyeye FERMİ DÜZEYİ diyoruz bu düzeyden sonraki üst enerji seviyelerini yani elektronların olmadığı boş enerji seviyelerini  dolu olan yani elektronlarca PAULİ seçim ilkesinde yerleşen elektronların bulunduğu seviyeyi bir birinden ayıran çizgiye Fermi Enerji Seviyesi ve buranın enerjisine da Fermi Enerjisi diyoruz.

Fermi Enerji seviyesi sıcaklığın etkisiyle üst seviyelere doğru kayabilir sebebi elektronların sıcaklığın artmasıyla üst seviyelere geçebilirler. Üst seviyeye geçildikçe de dolu kısımla boş kısım arasındaki seviye de üste doğru kayacaktır.

Katkısız olan benim fermi enerji seviyem  üst(boş) kısım ile alt(dolu) kısmın tam ortasında, eğer N Tipi olursam Fermi Enerji seviyem İletim bandının hemen altındaki bölgeye, yada P tipi olursamda Valans bandının hemen üstündeki bölgeye hareket etmeyi planlıyorum.

Makul Şüpheli olmamak için Buyurun Size Elektronikçe Tepki.