İçeriğe atla

Sonlu durum makinesi

Ş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.

Kavramlar

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 ADurum BDurum 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

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

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

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

Donanım uygulamaları

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ı

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

  • olay güdümlü SDM
  • sanal SDM (SSDM)
  • Otomata tabanlı programlama

Ayrıca bakınız

Dış bağlantılar

İngilizce

Kaynakça

  • 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

İlgili Araştırma Makaleleri

Sayı, sayma, ölçme ve etiketleme için kullanılan bir matematiksel nesnedir. En temel örnek, doğal sayılardır. Sayılar, sayı adı (numeral) ile dilde temsil edilebilir. Daha evrensel olarak, tekil sayılar rakam adı verilen sembollerle temsil edilebilir; örneğin, "5" beş sayısını temsil eden bir rakamdır. Yalnızca nispeten az sayıda sembolün ezberlenebilmesi nedeniyle, temel rakamlar genellikle bir rakam sisteminde organize edilir, bu da herhangi bir sayıyı temsil etmenin organize bir yoludur. En yaygın rakam sistemi Hint-Arap rakam sistemidir, bu sistem on temel sayısal sembol, yani rakam kullanılarak herhangi bir negatif olmayan tam sayının temsil edilmesine olanak tanır. Sayılar sayma ve ölçme dışında, etiketlerde, sıralamada ve kodlarda kullanılmak için de sıklıkla kullanılır. Yaygın kullanımda, bir rakam ile temsil ettiği sayı net bir şekilde ayrılmaz.

<span class="mw-page-title-main">Doğal sayılar</span> sayma sayıları kümesine 0ın eklenmesiyle oluşan sayılar kümesi

Doğal sayılar, şeklinde sıralanan tam sayılardır ve kimi tanımlamalara göre 0 sayısı da bu kümeye dâhil edilebilir. Aralarında standart ISO 80000-2'nin de bulunduğu bazı tanımlar doğal sayıları 0 ile başlatır ve bu durum negatif olmayan tam sayılar için 0, 1, 2, 3, ... şeklinde bir karşılık bulurken, bazı tanımlamalar 1 ile başlamakta ve bu da pozitif tam sayılar için 1, 2, 3, ... şeklinde bir eşlenik oluşturur. Doğal sayıları sıfır olmadan ele alan metinlerde, sıfırın da dahil edildiği doğal sayılar bazen tam sayılar olarak adlandırılırken diğer bazı metinlerde bu terim, negatif tam sayılar da dahil olmak üzere tam sayılar için kullanılmaktadır. Özellikle ilkokul seviyesindeki eğitimde, doğal sayılar, negatif tam sayıları ve sıfırı dışlamak ve saymanın ayrık yapısını, gerçek sayıların bir karakteristiği olan ölçümün sürekliliğiyle karşıtlık oluşturmak amacıyla sayma sayıları olarak adlandırılabilir.

<span class="mw-page-title-main">DNA bilgisayarları</span>

DNA bilgisayarı veya DNA hesaplaması, geleneksel silikon temelli yapı bileşenleri veya bilgisayar teknolojileri yerine, DNA, biyokimya ve moleküler biyoloji kullanarak yapılan bir hesaplama biçimi hesap edilen yeni nesil bilgisayarlardır. DNA hesaplaması veya daha genel olarak biyomoleküler hesaplama, hızla gelişen, disiplinler arası bir sahadır. Bu sahadaki araştırma ve geliştirmenin konuları, DNA hesaplamasının teorisi, uygulaması ve bu konuda yapılan deneyleri kapsar. Hacmi sadece 1 cm³ olan 1 gram DNA, 750 terabayt bilgi barındırabilir.

<span class="mw-page-title-main">Maddenin hâlleri</span> maddenin farklı aşamalarında yer alan farklı hâlleri

Bir fizik terimi olarak maddenin hâli, maddenin aldığı farklı fazlardır. Günlük hayatta maddenin dört farklı hâl aldığı görülür. Bunlar; katı, sıvı, gaz ve plazmadır. Maddenin başka hâlleri de bilinir. Örneğin; Bose-Einstein yoğunlaşması ve nötron-dejeneje maddesi. Fakat bu hâller olağanüstü durumlarda gerçekleşir, çok soğuk ya da çok yoğun maddelerde. Maddenin diğer hâllerininde, örneğin quark-gluon plazmalar, mümkün olduğuna inanılır fakat şu an sadece teorik olarak bilinir. Tarihsel olarak, maddenin özelliklerindeki niteleyici farklılıklara dayanarak ayrım yapılır. Katı hâldeki madde bileşen parçaları ile bir arada tutulur ve böylece sabit hacim ve şeklini korur. Sıvı hâldeki madde hacmini korur fakat bulunduğu kabın şeklini alır. Bu parçalar bir arada tutulur ama hareketleri serbesttir. Gaz hâlindeki madde ise hem hacim olarak hem de şekil olarak bulunduğu kaba ayak uydurur.Bu parçalar ne beraber ne de sabit bir yerde tutulur. Maddenin plazma hâli ise, nötr atomlarda dahil, hacim ve şekil olarak tutarsızdır. Serbestçe ilerleyen önemli sayıda iyon ve elektron içerirler. Plazma, evrende maddenin en yaygın şekilde görülen hâlidir.

Belirlenimsiz Turing makinesi, bulunduğu durumdan sonraki durum için birden fazla seçenek Turing makinasıdır. Makina aşağıdaki bileşenlerden oluşur:

<span class="mw-page-title-main">Lineer cebir</span> Uzay matematiği

Doğrusal cebir ya da lineer cebir; matematiğin, vektörler (yöney), vektör uzayları, doğrusal dönüşümler, doğrusal denklem takımları ve matrisleri (dizey) inceleyen alanıdır. Vektör uzayları, modern matematiğin merkezinde yer alan bir konudur. Bundan dolayı doğrusal cebir hem soyut cebirde hem de fonksiyonel analizde sıkça kullanılır. Doğrusal cebir, analitik geometri ile de alakalı olup sosyal bilimlerde ve fen bilimlerinde yaygın bir uygulama alanına sahiptir.

<span class="mw-page-title-main">Merkezî işlem birimi tasarımı</span>

Merkezî işlem birimi tasarımı bilgisayarın temel bileşenlerinden birisi olan Merkezî işlem birimini (MİB) etkin kullanmayı yönelik bir tasarımdır. MİB bilgisayar donanımının temel bileşenlerinden birisidir. İşlemcisi olmayan bir bilgisayar düşünülemez. Bu yüzden işlemcinin tasarımı ne kadar iyi olursa sistem de o derece hızlı olacaktır. İşlemciyi hızlandırmanın değişik yolları vardır. Bunlardan bazıları:

  1. Buyrukların paralel çalışmasını sağlamak
  2. Çok vuruşluk işlemciler kullanmak
  3. Boru hattı kullanmak
  4. Çoklu işleme kullanmak

Matematikte, Markov Zinciri, Markov özelliğine sahip bir stokastik süreçtir. Markov özelliğine sahip olmak, mevcut durum verildiğinde, gelecek durumların geçmiş durumlardan bağımsız olması anlamına gelir. Bir başka deyişle, mevcut durumun açıklaması, sürecin gelecekteki evrimini etkileyebilecek tüm bilgiyi kapsar. Gelecek durumlara belirli bir şekilde değil, olasılıksal bir süreçle ulaşılacaktır.

<span class="mw-page-title-main">Cebirsel sayılar</span>

Cebirsel sayılar, rasyonel katsayıları olan tek değişkenli sıfırdan farklı bir polinomun kökü olarak ifade edilebilen sayılardır. Mesela, altın oran, , cebirsel bir sayı örneğidir çünkü x2x − 1 polinomunun bir köküdür. Bu durumda, söz konusu polinomun değerinin sıfıra eşitlendiği x değeridir. Diğer bir örnek olarak, biçimindeki karmaşık sayı, x4 + 4 polinomunun bir kökü olduğundan dolayı cebirsel sayı olarak kabul edilir.

<span class="mw-page-title-main">Sayısal analiz</span>

Sayısal analiz, diğer adıyla nümerik analiz veya sayısal çözümleme, matematiksel analiz problemlerinin yaklaşık çözümlerinde kullanılan algoritmaları inceler. Bu nedenle birçok mühendislik dalı ve doğa bilimlerinde önem arz eden sayısal analiz, bilimsel hesaplama bilimi olarak da kabul edilebilir. Bilgisayarın işlem kapasitesinin artması ile gündelik hayatta ortaya çıkan birçok sistemin matematiksel modellenmesi mümkün olmuş ve sayısal analiz algoritmaları burada ön plana çıkmıştır. 21. yüzyıldan itibaren bilimsel hesaplama yöntemleri mühendislik ve doğa bilimleri ile sınırlı kalmamış ve sosyal bilimler ile işletme gibi alanları da etkilemiştir. Sayısal analizin alt başlıklarına adi diferansiyel denklemlerin yaklaşık çözümleri ve özellikle veri biliminde önem taşıyan sayısal lineer cebir ile optimizasyon örnek gösterilebilir.

<span class="mw-page-title-main">Kuantum alan teorisi</span> hareketli parçacık sistemlerinin kuantizasyonuyla ilgilenen parçacık mekaniğiyle benzer olarak, alanların hareketli sistemlerine parçacık mekaniğinin uygulamasıdır

Kuantum Alan Teorisi (METATEORİ); Klasik Birleşik Alan (KAT) Teorilerini, Özel Görekliliği (SRT), Kuantum mekaniği (KM) teorilerini tek bir teorik çerçeve altında toplayan bir üst teoridir.

Olasılık kuramında Borel–Cantelli önermesi olay dizilerine ilişkin bir savdır. Ölçü kuramının bir sonucu olan önerme Émile Borel ve Francesco Paolo Cantelli'ye adanmıştır.

Matematiksel model, bir sistemin matematiksel kavramlar ve dil kullanılarak tanımlanmasıdır. Matematiksel model geliştirme süreci, matematiksel modelleme olarak adlandırılır. Matematiksel modeller, doğa bilimlerinde ve mühendislik disiplinlerinde bunun yanı sıra sosyal bilimlerde kullanılır. Matematiksel modelleri daha çok fizikçiler, mühendisler, istatistikçiler, operasyon araştırma analistleri ve ekonomistler kullanır. Model, bir sistemi açıklamaya, farklı bileşenlerin etkilerini incelemeye ve bir davranış hakkında öngörüde bulunmak için yardımcı olabilir.

Dijital Devre teorisinde, “Sıralı Mantık” devrenin çıktılarının sadece şu anki durumuna değil, aynı zamanda geçmişteki Dijital Sinyal girdilerine de bağlı olduğu mantık devresi yapısıdır. Sıralı mantık devreleri kombinasyonel mantık devrelerinin aksine sadece şu anki inputlara bağlı değildir. Şöyle ki, sıralı mantık devrelerinin durum hafızaları varken, kombinasyonel mantık devrelerinin yoktur. Diğer bir deyişle, sıralı mantık devreleri hafıza elemanı taşıyan kombinasyonel devrelerdir.

<span class="mw-page-title-main">Termodinamik durum</span>

Termodinamikte, sistemin termodinamik durumu, durum fonksiyonları olarak bilinen uygun değişken değerleriyle tam olarak tanımlanabilir. Termodinamik değişkenlerinin değerleri bir sistem için bir kere belirlendiğinde, termodinamiğin bütün özelliklerinin değerleri eşsiz bir şekilde belirlenmiş olur. Genellikle, termodinamik durum termodinamik dengenin biri olarak varsayılır. Yani, bu durum bir sistemin sadece belli bir süredeki durumu değil, durum süresiz uzunlukta aynı ve değişmezdir.

Stokastik süreç, Stokastik işlemi, zaman veya mekana göre değişen/evrilen olguları tanımlamak için kullanılan bir olasılık modelidir. Daha kapsamlı olarak, olasılık teorisinde, stokastik süreç, değişimi rastgele bir varyasyona bağlı olan bir değişken tarafından temsil edilen bazı sistemlerin gelişimini yansıtan bir zaman dizisidir. Bu, belirleyici süreç anlamına gelen deterministik sürecin olasılıkçı muadilidir. Sadece tek yönlü olarak değişebilen bir süreci tasvir etmek yerine bir stokastik veya rastgele süreçte, bazı belirsizlikler vardır. Hatta başlangıçtaki durum biliniyor olsa dahi sürecin gelişebileceği/değişebileceği bazı yönler vardır. Birçok stokastik süreçte, bir sonraki duruma veya konuma geçiş, yalnızca mevcut duruma bağlıdır ve işlemin önceki durumlarından veya değerlerinden bağımsızdır.

<span class="mw-page-title-main">Pekiştirmeli öğrenme</span>

Pekiştirmeli öğrenme, davranışçılıktan esinlenen, öznelerin bir ortamda en yüksek ödül miktarına ulaşabilmesi için hangi eylemleri yapması gerektiğiyle ilgilenen bir makine öğrenmesi yaklaşımıdır. Bu problem, genelliğinden ötürü oyun kuramı, kontrol kuramı, yöneylem araştırması, bilgi kuramı, benzetim tabanlı eniyileme ve istatistik gibi birçok diğer dalda da çalışılmaktadır.

<span class="mw-page-title-main">Zamanda sonlu farklar yöntemi</span> elektromanyetizmada kullanılan bir yöntem

Zamanda sonlu farklar yöntemi, kısaca FDTD ya da Yee yöntemi, hesaplamalı elektromanyetizmada kullanılan bir sonlu farklar tekniğidir. Zaman düzleminde çalışan bir yöntem olduğundan ötürü, elektromanyetik spektrumun mikrodalga veya görünür ışık gibi farklı bölgelerinde anten veya fotonik aygıt tasarımı gibi çeşitli problemlerin çözümünde kullanılır. Aynı zamanda bu özellik, simülasyonu yapılan sistemin geniş bir frekans yelpazesine tepkisinin gözlenebilmesini sağlamaktadır. Matris tersinmesi gerektirmeyen bu FDTD, en yaygın elektromanyetik simülasyon yöntemlerinden biri olarak kabul edilir.

Bilgi teknolojisi ve bilgisayar biliminde eğer önceki olayları veya kullanıcı etkileşimlerini hatırlamak için tasarlandıysa biliminde bir sistem durumsal olarak ifade edilmiştir, hatırlanan bilgiye ise sistemin durumu denir.

<span class="mw-page-title-main">Ölçü (matematik)</span> uzunluk, alan, hacim ve integralin bir genellemesi olarak görülebilecek bir kümenin bazı alt kümelerine sayılar atayan işlev

Matematiksel analizde, küme üzerindeki bir ölçü, bu kümenin her bir uygun alt kümesine bir sayı atamanın sistematik bir yoludur ve sezgisel olarak kümenin boyutu olarak yorumlanır. Bu anlamda ölçü, uzunluk, alan ve hacim kavramlarının bir genellemesidir. Özellikle önemli bir örnek, Öklid geometrisinin geleneksel uzunluğunu, alanını ve hacmini n-boyutlu Öklid uzayının Rn uygun alt kümelerine atayan bir Öklid uzayındaki Lebesgue ölçüsüdür. Örneğin, gerçek sayılardaki [0, 1] aralığının Lebesgue ölçüsü, kelimenin günlük anlamındaki uzunluğudur ve tam olarak 1'dir.