İçeriğe atla

Sonlu durum makinesi

Vikipedi, özgür ansiklopedi
Şekil.1 Sonlu durum makinası

Sonlu durum makinası (veya sonlu durum otomatı veya basitçe durum makinası); sınırlı sayıda durumdan, durumlar arası geçişlerden ve eylemlerin birleşmesiyle oluşan davranışların bir modelidir.

Durum geçmiş hakkında bilgi saklar, örneğin başlangıçtan şu anki duruma kadar girdi değişimlerini gösterir. Geçiş durum değişimini gösterir ve geçişi sağlamak için yapılması gereken koşulla tanımlanır. Eylem belirli bir zamanda gerçekleştirilen etkinliğin tanımıdır. Birçok eylem tipi vardır:

Giriş eylemi
Bu eylem duruma geçerken gerçekleştirilir
Çıkış eylemi
Bu eylem durumdan çıkarken gerçekleştirilir
Girdi eylemi
Mevcut duruma ve girdi koşullarına bağlı gerçekleştirilen eylemdir
Geçiş eylemi
Belirli bir geçiş gerçekleştirilirken oluşan eylemdir

SDM durum çizgeleriyle (veya geçiş çizgeleriyle) temsil edilir (Bkz. Şekil 1). Bunun dışında çok sayıda durum geçiş tablo tipleri kullanılmaktadır. En çok karşılaşılan temsil aşağıda gösterilmiştir: mevcut durum (B)'de iken koşul (Y) gerçekleştiğinde sonraki durum (C) ortaya çıkar. Tüm eylemlerin bilgisi ancak dipnot kullanımıyla eklenebilmektedir. Tüm eylemlerin bilgisini içeren bir SDM tanımı durum tablolarını kullanarak mümkündür (Bkz. Sanal Sonlu Durum Makinası).

Durum Geçiş Tablosu

   Mevcut Durum →
Koşul
Durum A Durum B Durum C
Koşul X ... ... ...
Koşul Y ... Durum C ...
Koşul Z ... ... ...

Burada gösterilen tepkisel sistemleri modellemeye ek olarak, sonlu durum makinaları çok farklı alanda önemlidir, bu alanlar elektrik mühendisliği, dilbilim, bilgisayar bilimleri, felsefe, biyoloji, matematik ve mantık olarak sayılabilir. Sonlu durum makinaları otomata teorisi ve hesaplama teorisinde çalışılan otomatların bir sınıfıdır. Bilgisayar bilimlerinde, sonlu durum makinaları uygulama davranışı, donanım sayısal sistemlerinin tasarımı, yazılım mühendisliği, ağ protokolleri ve hesaplama ve dillerin öğretilmesinde geniş ölçüde kullanılmaktadır.

Sınıflandırma

[değiştir | kaynağı değiştir]

Alıcı ("Acceptor")/Tanıyıcı ("Recognizer") ve dönüştürücü ("Transducer") olmak üzere iki farklı grup vardır.

Alıcılar/Tanıyıcılar

[değiştir | kaynağı değiştir]

Alıcılar ve tanıyıcılar girdinin makina tarafından kabul edilip edilmediğini belirten evet/hayır (0 veya 1, ikili çıktı) cevaplarından birini verirler. SDM'nın tüm durumlarının kabul eden veya kabul etmeyen olması gerekir. Girdiler işlenirken, mevcut durum kabul eden bir durumsa, girdi kabul edilir; kabul etmeyen bir durumsa girdi reddedilir. Kural olarak girdiler için karakterler sembol olarak kullanılır, eylemler yoktur.

Makina ayrıca makinenin kabul ettiği tüm kelimeleri içeren, makinenin reddettiği tüm kelimeleri içermeyen dil olarak tanımlanabilir. Tanım gereği, SDM'ler tarafından kabul edilen diller Düzenli Diller'dir, bu ifade ayrıca bir dilin kendisini kabul eden SDM olması durumunda düzenli bir dil olduğunu gösterir (Bkz. Kleene Teoremi).

Başlangıç durumu
Başlangıcı gösteren ve "Start" ifadesiyle veya hiçbir yerden gelen bir okla gösterilen durumdur.
Kabul durumu
Makinanın yordamını başarıyla gerçekleştirdiği durumdur. Çift halka ile temsil edilir. Yordamın bitişini gösterir.

Yukarıdaki şekilde çift sayıda sıfır içeren ikili ifadeleri oluşturan deterministik sonlu otomata örneği görülmektedir. Soldan gelen ok sayesinde S1'in başlangıç durumu olduğunu ve iç içe çift halka sayesinde de yine S1'in kabul durum olduğunu anlayabiliyoruz. Bu şekilde ifadede bir sıfır geldiği zaman S2'e geçerek ek olarak mutlaka bir sıfır daha ekleneceği garantilenmiş oluyor ve her zaman kabul edilen ifade çift sayıda sıfır içeriyor.

Dönüştürücüler

[değiştir | kaynağı değiştir]

Dönüştürücüler, verilen girdi ve eylemleri kullanarak ortaya çıkan durumlara dayanarak çıktı üretirler. Kontrol uygulamaları için kullanılırlar. İki farklı tipi aşağıda anlatılmaktadır.

Moore makinası
SDM sadece giriş eylemlerini kullanır, çıkış duruma bağlıdır. Moore modelinin avantajı davranışın basitleşmesidir. Şekil 3 asansör kapısı Moore SDM'sini göstermektedir. Durum makinası iki komutu tanımaktadır: "command_open" ve "command_close" ve bu komutlar durum geçişlerini tetikler. "Opening" durumunda girdi eylemi (E:) kapıyı açan bir motoru başlatır, "Closing" durumundaki girdi eylemi ise motoru kapıyı kapatma yönünde çalıştırır. "Opened" ve "Closed" durumları herhangi bir eylem gerçekleştirmez. Dış dünyaya (örneğin diğer durum makinalarına) vaziyeti bildirirler: "door is open" (kapı açık) veya "door is closed" (kapı kapalı).
Şekil 4 Dönüştürücü SDM: Mealy model örneği
Mealy makinası
SDM sadece girdi eylemlerini kullanır, çıktı girdi ve duruma bağlıdır. Mealy SDM'lerinin kullanımı durum sayısının azalmasını sağlamaktadır. Şekil 4'teki örnek Şekil 3'teki Moore makinasıyla aynı işi yapan Mealy makinasını göstermektedir. İki girdi eylemi vardır (I:) : "command_close gelirse kapıyı kapatmak için motoru başlat" ve "command_open gelirse kapıyı açmak için motoru diğer yönde başlat".

Pratikte bu iki modelin karışımları kullanılmaktadır.

Ayrıca deterministik (DFA) ve deterministik olmayan (NDFA) ayrımı vardır. Deterministik otomatada, her durum için, olası her girdiye karşılık gelen bir geçiş vardır. Deterministik olmayan otomatada, bir durumdan bir girdi için hiç, bir veya daha fazla geçiş olabilmektedir. Bu ayrım pratikte anlamlıdır ancak teoride NDFA'yı eşit bir DFA'ya dönüştüren bir algoritma olması -bu dönüşüm her ne kadar otomatanın karmaşıklığını artırsa da- dolayısıyla önemsizdir.

Gerçekleştirim

[değiştir | kaynağı değiştir]

Donanım uygulamaları

[değiştir | kaynağı değiştir]

Sonlu durum makinaları sayısal devrelerde; programlanabilir mantık cihazı, programlanabilir mantık kontrolcüsü, mantık kapıları ve Flip-floplar veya anahtarlar kullanılarak gerçekleştirilebilir. Daha belirgin olursak, donanım gerçekleştirimi durum değişkenlerini saklamak için işlemci yazmaçı, durum geçişine karar veren kombinasyonel mantık bloku ve SDM'nin çıktısına karar veren başka bir kombinasyonel mantık blokuna ihtiyaç duyulur. Klasik donanım gerçekleştirimlerine örnek olarak Richard's Controller verilebilir.

Yazılım uygulamaları

[değiştir | kaynağı değiştir]

Aşağıdaki kavramlar sonlu durum makinalarıyla yazılım uygulaması üretmek için genellikle kullanılırlar:

Ayrıca bakınız

[değiştir | kaynağı değiştir]

Dış bağlantılar

[değiştir | kaynağı değiştir]
  • Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, ISBN 0-8493-8086-3.
  • Samek, M., "Practical Statecharts in C/C++", CMP Books, 2002, ISBN 1-57820-110-1.
  • Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, ISBN 0-7923-8609-4.
  • Timothy Kam, Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
  • Tiziano Villa, Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
  • Carroll, J., Long, D., Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall, Englewood Cliffs, 1989.
  • Kohavi, Z., Switching and Finite Automata Theory. McGraw-Hill, 1978.
  • Gill, A., Introduction to the Theory of Finite-state Machines. McGraw-Hill, 1962.
  • Ginsburg, S., An Introduction to Mathematical Machine Theory. Addison-Wesley, 1962.
  • Cohen, D. I. A., Introduction to Computer Theory. Wiley, 1996. ISBN 0-471-13772-3