Sonlu durum makinesi - Finite-state machine
Bir sonlu-durum makinesi ( FSM ) veya sonlu-durum otomatı ( FSA , çoğul: otomata ), sonlu otomat veya basitçe bir durum makinesi , matematiksel bir hesaplama modelidir . Bu bir olan soyut makine tam olarak bir sonlu sayıda olabilir devletler herhangi bir zamanda. FSM, bazı girdilere yanıt olarak bir durumdan diğerine geçebilir ; bir durumdan diğerine geçişe geçiş denir . Bir FSM, durumlarının, başlangıç durumunun ve her geçişi tetikleyen girdilerin bir listesiyle tanımlanır. Sonlu durum makineleri iki tiptir - deterministik sonlu durum makineleri ve deterministik olmayan sonlu durum makineleri . Bir deterministik sonlu durum makinesi, deterministik olmayan herhangi bir makineye eşdeğer olarak oluşturulabilir.
Durum makinelerinin davranışı, sunuldukları olaylar dizisine bağlı olarak önceden belirlenmiş bir dizi eylem gerçekleştiren modern toplumdaki birçok aygıtta gözlemlenebilir. Basit örnekler , uygun madeni para kombinasyonu yatırıldığında ürün dağıtan otomatlar , durak sırası binicilerin talep ettiği katlara göre belirlenen asansörler , arabalar beklerken sırayı değiştiren trafik ışıkları ve gerekli olan şifreli kilitlerdir. uygun sırayla bir dizi sayının girişi.
Sonlu durum makinesi, Turing makinesi gibi diğer bazı hesaplama modellerinden daha az hesaplama gücüne sahiptir . Hesaplama gücü ayrımı, bir Turing makinesinin yapabileceği, ancak bir FSM'nin yapamayacağı hesaplama görevleri olduğu anlamına gelir. Bunun nedeni, bir FSM'nin belleğinin sahip olduğu durum sayısı ile sınırlı olmasıdır. Sonlu durumlu bir makine, kafası yalnızca "okuma" işlemlerini gerçekleştirebilecek ve her zaman soldan sağa hareket etmesi gereken şekilde kısıtlanmış bir Turing makinesiyle aynı hesaplama gücüne sahiptir. FSM'ler daha genel otomata teorisi alanında incelenir .
Örnek: jetonlu turnike
Bir durum makinesi tarafından modellenebilen basit bir mekanizmaya örnek bir turnikedir . Metrolara ve eğlence parkı gezilerine erişimi kontrol etmek için kullanılan bir turnike, biri giriş yolunun karşısında olmak üzere bel yüksekliğinde üç döner kolu olan bir kapıdır. Başlangıçta kollar kilitlenir, girişi engeller, müşterilerin geçmesini engeller. Turnike üzerindeki bir yuvaya jeton veya jeton yatırmak, kolların kilidini açarak tek bir müşterinin geçmesine izin verir. Müşteri geçtikten sonra, başka bir madeni para girene kadar kollar tekrar kilitlenir.
Durum makinesi olarak kabul edilen turnikenin iki olası durumu vardır: Kilitli ve Kilitsiz . Durumunu etkileyen iki olası giriş vardır: yuvaya bozuk para koymak ( jeton ) ve kolu itmek ( itmek ). Kilitli durumda kolu itmenin bir etkisi yoktur; input push'u kaç kez verilirse verilmiyor, kilitli durumda kalır. Bir para koymak - olduğundan, makineyi bir vererek sikke girdi - dan durumunu kaydırır Kilitli için Kilitli . Kilit açık durumdayken, ek para koymanın bir etkisi olmaz; yani ek jeton girişi verilmesi durumu değiştirmez. Ancak, bir müşteri kolları iterek, bir itme girdisi vererek durumu tekrar Kilitli olarak değiştirir .
Turnike durum makinesi, her olası durum için aralarındaki geçişleri (makineye verilen girdilere dayalı olarak) ve her bir girdiden kaynaklanan çıktıları gösteren bir durum geçiş tablosu ile temsil edilebilir :
Şu anki durum Giriş Sonraki Durum Çıktı Kilitli madeni para kilidi açıldı Müşterinin geçebilmesi için turnikenin kilidini açar. itmek Kilitli Hiçbiri kilidi açıldı madeni para kilidi açıldı Hiçbiri itmek Kilitli Müşteri ittiğinde turnikeyi kilitler.
Turnike durum makinesi, durum diyagramı (yukarıda) adı verilen yönlendirilmiş bir grafikle de temsil edilebilir . Her durum bir düğüm ( daire ) ile temsil edilir . Kenarlar ( oklar ) bir durumdan diğerine geçişleri gösterir. Her ok, bu geçişi tetikleyen girdiyle etiketlenir. Durum değişikliğine neden olmayan bir girdi ( Kilidi Açık durumdaki bozuk para girişi gibi ), orijinal durumuna dönen dairesel bir okla temsil edilir. Siyah noktadan Kilitli düğümün içindeki ok , bunun başlangıç durumu olduğunu gösterir.
Kavramlar ve terminoloji
Bir devlet bir yürütmek için bekleyen bir sistemin durumunun tanımıdır geçişi . Geçiş, bir koşul yerine getirildiğinde veya bir olay alındığında yürütülecek bir dizi eylemdir. Örneğin, radyo dinlemek için bir ses sistemi kullanırken (sistem "radyo" durumundadır), bir "sonraki" uyarıcının alınması bir sonraki istasyona geçilmesine neden olur. Sistem "CD" durumundayken, "sonraki" uyarıcı bir sonraki parçaya geçilmesiyle sonuçlanır. Aynı uyaranlar, mevcut duruma bağlı olarak farklı eylemleri tetikler.
Bazı sonlu durum makine temsillerinde, eylemleri bir durumla ilişkilendirmek de mümkündür:
- bir giriş eylemi: duruma girilirken gerçekleştirilir ve
- çıkış eylemi: durumdan çıkarken gerçekleştirilir .
temsiller
Durum/Olay tablosu
Birkaç durum geçiş tablosu türü kullanılır. En yaygın gösterim aşağıda gösterilmiştir: mevcut durum (örneğin B) ve giriş (örneğin Y) kombinasyonu bir sonraki durumu (örneğin C) gösterir. Tam eylemin bilgileri doğrudan tabloda açıklanmaz ve yalnızca dipnotlar kullanılarak eklenebilir. Durum tabloları kullanılarak tam eylemin bilgilerini içeren bir FSM tanımı mümkündür (ayrıca bkz. sanal sonlu durum makinesi ).
Mevcut
durum Giriş
|
Devlet A | B durumu | Devlet C |
---|---|---|---|
X girişi | ... | ... | ... |
Y girişi | ... | Devlet C | ... |
Z girişi | ... | ... | ... |
UML durum makineleri
Unified Modeling Language durum makineleri tanımlamak için bir gösterim var. UML durum makineleri , ana faydalarını korurken geleneksel sonlu durum makinelerinin sınırlamalarının üstesinden gelir. UML durum makineleri , eylem kavramını genişletirken, hiyerarşik olarak iç içe geçmiş durumlar ve ortogonal bölgelerin yeni kavramlarını sunar . UML durum makineleri hem özelliklere sahip Mealy makineleri ve Moore makineleri . Onlar destekleyen eylemleri sisteminin durumu ve tetikleme hem bağlıdır olay Mealy makinelerinde olduğu gibi, aynı zamanda giriş ve çıkış işlemleri Moore makinelerinde olduğu gibi, devletler yerine geçişler ile ilişkilidir.
SDL durum makineleri
Şartname ve Tanımlama Dili bir standarttır ITU o geçişte eylemleri tanımlamak için grafiksel semboller içermektedir:
- bir etkinlik gönder
- bir etkinlik almak
- zamanlayıcı başlat
- zamanlayıcıyı iptal et
- başka bir eşzamanlı durum makinesini başlat
- karar
SDL, sonlu durum makinesini yürütülebilir kılmak için "Özet Veri Türleri" olarak adlandırılan temel veri türlerini, bir eylem dilini ve bir yürütme semantiğini gömer.
Diğer durum diyagramları
Şekil 3'teki gibi bir FSM'yi temsil etmek için çok sayıda varyant vardır.
kullanım
Burada sunulan reaktif sistemleri modellemede kullanımlarına ek olarak, sonlu durum makineleri, elektrik mühendisliği , dilbilim , bilgisayar bilimi , felsefe , biyoloji , matematik , video oyun programlama ve mantık dahil olmak üzere birçok farklı alanda önemlidir . Sonlu durum makineleri, otomata teorisi ve hesaplama teorisinde incelenen bir otomat sınıfıdır . Bilgisayar biliminde, sonlu durum makineleri, uygulama davranışının modellenmesinde, donanım dijital sistemlerinin tasarımında , yazılım mühendisliğinde , derleyicilerde , ağ protokollerinde ve hesaplama ve dil çalışmalarında yaygın olarak kullanılmaktadır .
sınıflandırma
Sonlu durum makineleri, alıcılara, sınıflandırıcılara, dönüştürücülere ve sıralayıcılara bölünebilir.
alıcılar
Alıcılar ( algılayıcılar veya tanıyıcılar olarak da adlandırılır ), alınan girdinin kabul edilip edilmediğini gösteren ikili çıktı üretir. Bir kabul edenin her durumu ya kabul ediyor ya da etmiyor . Tüm girdiler alındıktan sonra, mevcut durum bir kabul durumu ise, girdi kabul edilir; aksi halde reddedilir. Kural olarak, girdi bir semboller (karakterler) dizisidir ; eylemler kullanılmaz. Başlangıç durumu aynı zamanda kabul eden bir durum da olabilir, bu durumda alıcı boş dizeyi kabul eder. Şekil 4'teki örnek, "nice" dizesini kabul eden bir alıcıyı göstermektedir. Bu alıcıda, tek kabul eden durum 7 durumudur.
Bir adlandırılan sembol dizilerinin A (muhtemelen sonsuz) seti, biçimsel dil , bir olan normal dil kabul bazı alıcı varsa tam olarak bu kümeyi. Örneğin, çift sayıda sıfıra sahip ikili dizeler kümesi normal bir dildir (bkz. Şekil 5), uzunluğu asal sayı olan tüm dizelerin kümesi ise normal bir dil değildir.
Bir alıcı, kabul eden tarafından kabul edilen her dizeyi içeren ancak reddedilenlerin hiçbirini içermeyen bir dil tanımlaması olarak da tanımlanabilir; bu dil alıcı tarafından kabul edilir. Tanım olarak, alıcılar tarafından kabul edilen diller normal dillerdir .
Belirli bir alıcı tarafından kabul edilen dili belirleme sorunu, cebirsel yol sorununun bir örneğidir - kendisi de en kısa yol sorununun (keyfi) bir yarı halkanın öğeleriyle ağırlıklandırılmış kenarları olan grafiklere genelleştirilmesidir .
Kabul eden duruma bir örnek Şekil 5'te görülmektedir: ikili giriş dizisinin çift sayıda 0 içerip içermediğini tespit eden deterministik bir sonlu otomat (DFA) .
S 1 (aynı zamanda başlangıç durumudur), çift sayıda 0'ların girildiği durumu gösterir. S 1 bu nedenle kabul eden bir durumdur. Bu alıcı, ikili dize çift sayıda 0 içeriyorsa (0'ları içermeyen herhangi bir ikili dize dahil) kabul durumunda sona erecektir. Bu alıcı tarafından kabul edilen dize örnekleri ε ( boş dize ), 1, 11, 11..., 00, 010, 1010, 10110, vb.'dir.
sınıflandırıcılar
Sınıflandırıcılar bir üreten alıcıların genelleme olarak N -ary çıkış n iki daha sıkı bir şekilde daha fazladır.
dönüştürücüler
Dönüştürücüler , eylemleri kullanarak belirli bir girdiye ve/veya bir duruma dayalı olarak çıktı üretir. Kontrol uygulamaları için ve hesaplamalı dilbilim alanında kullanılırlar .
Kontrol uygulamalarında iki tip ayırt edilir:
- Moore makinesi
- FSM yalnızca giriş eylemlerini kullanır, yani çıktı yalnızca duruma bağlıdır. Moore modelinin avantajı, davranışın basitleştirilmesidir. Bir asansör kapısı düşünün. Durum makinesi iki komutu tanır: durum değişikliklerini tetikleyen "command_open" ve "command_close". "Açma" durumundaki giriş eylemi (E:) kapıyı açan bir motoru çalıştırır, "Kapanıyor" durumundaki giriş eylemi, kapıyı kapatan diğer yönde bir motoru çalıştırır. "Açık" ve "Kapalı" durumları, tamamen açıldığında veya kapatıldığında motoru durdurur. Dış dünyaya (örneğin, diğer durum makinelerine) durumu bildirirler: "kapı açık" veya "kapı kapalı".
- etli makine
- FSM ayrıca girdi eylemlerini kullanır, yani çıktı girdiye ve duruma bağlıdır. Bir Mealy FSM'nin kullanılması, genellikle durum sayısında bir azalmaya yol açar. Şekil 7'deki örnek, Moore örneğindekiyle aynı davranışı uygulayan bir Mealy FSM'yi göstermektedir (davranış, uygulanan FSM yürütme modeline bağlıdır ve örneğin sanal FSM için çalışacaktır, ancak olay güdümlü FSM için çalışmayacaktır ). İki giriş eylemi vardır (I:): "komut_kapama gelirse kapıyı kapatmak için motoru çalıştır" ve "komut_açma gelirse kapıyı açmak için motoru diğer yönde çalıştır". "Açılış" ve "kapanış" ara durumları gösterilmez.
Sıralayıcılar
Sıralayıcılar ( jeneratörler olarak da adlandırılır ), tek harfli bir giriş alfabesine sahip alıcıların ve dönüştürücülerin bir alt sınıfıdır. Alıcı veya dönüştürücü çıktılarının bir çıktı dizisi olarak görülebilen yalnızca bir dizi üretirler.
determinizm
Diğer bir ayrım, deterministik ( DFA ) ve deterministik olmayan ( NFA , GNFA ) otomatlar arasındadır. Deterministik bir otomatta, her durum, her olası giriş için tam olarak bir geçişe sahiptir. Deterministik olmayan bir otomatta, bir girdi, belirli bir durum için bir, birden fazla veya hiç geçişe yol açabilir. Güç kümesi oluşturma algoritması, herhangi bir deterministik olmayan otomatı, aynı işlevselliğe sahip (genellikle daha karmaşık) bir deterministik otomata dönüştürebilir.
Yalnızca bir durumu olan bir sonlu durum makinesine "kombinatoryal FSM" denir. Sadece geçiş üzerine eylemlerini verir içine bir devlet. Bu konsept, bir dizi sonlu durum makinesinin birlikte çalışması gerektiği durumlarda ve tasarım araçlarına uyması için tamamen kombinatoryal bir parçanın bir FSM biçimi olarak düşünülmesinin uygun olduğu durumlarda kullanışlıdır.
alternatif anlambilim
Durum makinelerini temsil etmek için kullanılabilen başka anlam kümeleri de vardır. Örneğin, gömülü denetleyiciler için mantık modelleme ve tasarlama araçları vardır. Onlar birleştirmek hiyerarşik durum makineleri (genellikle birden fazla mevcut durumunu sahip olan), grafikler ve akış doğruluk tabloları farklı bir formalitelere semantik setinde sonuçlanan bir dile. Bu grafikler, Harel'in orijinal durum makineleri gibi, hiyerarşik olarak iç içe geçmiş durumları, ortogonal bölgeleri , durum eylemlerini ve geçiş eylemlerini destekler.
Matematiksel model
Genel sınıflandırmaya uygun olarak aşağıdaki biçimsel tanımlar bulunur.
Bir deterministik sonlu-durum makinesi veya deterministik sonlu-durum alıcısı , beşli bir dir , burada:
- giriş alfabesidir (sonlu, boş olmayan bir sembol seti);
- sonlu, boş olmayan bir durum kümesidir;
- bir başlangıç durumudur, bir öğesidir ;
- durum-geçiş işlevidir: (belirleyici olmayan bir sonlu otomatta olur , yani bir dizi durum döndürür);
- son durumlar kümesidir, (muhtemelen boş) alt kümesidir .
Her iki deterministik-belirsiz FSMs için, izin vermek için geleneksel olan bir olmak kısmi fonksiyonu , örneğin, her bir kombinasyonu için tanımlandığı olmak zorunda değildir ve . Bir FSM durumunda ise, sonraki sembol tanımlıdır ve tanımlanmamıştır, o zaman bir hata bildirebilir (yani girişi reddedebilir). Bu, genel durum makinelerinin tanımlarında yararlıdır, ancak makineyi dönüştürürken daha az kullanışlıdır. Varsayılan biçimindeki bazı algoritmalar toplam işlev gerektirebilir.
Sonlu durumlu bir makine, kafası yalnızca "okuma" işlemlerini gerçekleştirebilecek ve her zaman soldan sağa hareket etmesi gereken şekilde kısıtlanmış bir Turing makinesiyle aynı hesaplama gücüne sahiptir. Yani, bir sonlu durum makinesi tarafından kabul edilen her bir biçimsel dil, bu tür bir kısıtlı Turing makinesi tarafından kabul edilir ve bunun tersi de geçerlidir.
Bir sonlu-durum dönüştürücüsü bir altılıktır , burada:
- giriş alfabesidir (sonlu, boş olmayan bir sembol seti);
- çıktı alfabesidir (sonlu, boş olmayan bir sembol seti);
- sonlu, boş olmayan bir durum kümesidir;
- başlangıç durumu, bir öğesidir ;
- durum geçiş işlevidir: ;
- çıkış fonksiyonudur.
Çıkış işlevi duruma ve giriş sembolüne ( ) bağlıysa, bu tanım Mealy modeline karşılık gelir ve bir Mealy makinesi olarak modellenebilir . Çıkış işlevi yalnızca duruma ( ) bağlıysa, bu tanım Moore modeline karşılık gelir ve bir Moore makinesi olarak modellenebilir . Hiçbir çıktı işlevi olmayan sonlu durumlu bir makine, yarı otomatik veya geçiş sistemi olarak bilinir .
Bir Moore makinesinin ilk çıktı sembolünü göz ardı edersek , o zaman, her Mealy geçişinin çıktı fonksiyonunu (yani her kenarı etiketleme) Moore hedefinden verilen çıktı sembolü ile ayarlayarak, çıktı eşdeğeri bir Mealy makinesine kolayca dönüştürülebilir. durum. Bir Mealy makine durumu, gelen geçişlerinde (kenarlarında) farklı çıktı etiketlerine sahip olabileceğinden, ters dönüşüm daha az basittir. Bu tür her bir durumun, her olay çıktı sembolü için bir tane olmak üzere, birden çok Moore makine durumuna bölünmesi gerekir.
Optimizasyon
Bir FSM'yi optimize etmek, aynı işlevi gerçekleştiren minimum sayıda duruma sahip bir makine bulmak anlamına gelir. Bunu yapan en hızlı bilinen algoritma Hopcroft minimizasyon algoritmasıdır . Diğer teknikler, bir çıkarım tablosunun veya Moore azaltma prosedürünün kullanılmasını içerir. Ek olarak, döngüsel olmayan FSA'lar doğrusal zamanda en aza indirilebilir.
uygulama
Donanım uygulamaları
Bir de , dijital devre , bir FSM bir kullanılarak inşa edilebilir programlanabilir mantık aygıtı , bir programlanabilir mantık denetleyicisi , mantık kapıları ve flip flop ya da röleler . Daha özel olarak ise, bir donanım uygulamasının bir gerektirir kayıt deposu durum değişkenlerine, bir blok kombinasyonel mantık durum geçişini belirler ve bir FSM çıkışını tespit kombinasyonel mantık ikinci bir blok. Klasik donanım uygulamalarından biri Richards denetleyicisidir .
Bir Medvedev makinesinde , çıkış, flip-floplar ve çıkış arasındaki zaman gecikmesini en aza indiren durum flip-floplarına doğrudan bağlanır.
Düşük güçlü durum makineleri için durum kodlaması sayesinde güç tüketimini en aza indirmek için optimize edilebilir.
Yazılım uygulamaları
Aşağıdaki kavramlar, sonlu durum makineleriyle yazılım uygulamaları oluşturmak için yaygın olarak kullanılır:
- Otomat tabanlı programlama
- Olay güdümlü sonlu durum makinesi
- Sanal sonlu durum makinesi
- Durum tasarım deseni
Sonlu durum makineleri ve derleyiciler
Sonlu otomatlar genellikle programlama dili derleyicilerinin ön ucunda kullanılır . Böyle bir ön uç, sözlüksel bir çözümleyici ve bir ayrıştırıcı uygulayan birkaç sonlu durum makinesi içerebilir . Bir karakter dizisinden başlayarak, sözcüksel çözümleyici, ayrıştırıcının bir sözdizimi ağacı oluşturduğu bir dizi dil belirteçleri (ayrılmış sözcükler, değişmez değerler ve tanımlayıcılar gibi) oluşturur. Sözcüksel çözümleyici ve ayrıştırıcı, programlama dilinin gramerinin düzenli ve bağlamdan bağımsız kısımlarını işler.
Ayrıca bakınız
- Soyut durum makineleri (ASM)
- Yapay zeka (AI)
- Soyut Durum Makine Dili (AsmL)
- davranış modeli
- İletişim kuran sonlu durum makinesi
- Kontrol sistemi
- Kontrol tablosu
- Karar tabloları
- DEVS : Ayrık Olay Sistemi Spesifikasyonu
- Genişletilmiş sonlu durum makinesi (EFSM)
- Veri yolu ile sonlu durum makinesi
- Gezel
- Gizli Markov modeli
- Hedef arama sırası
- Düşük güçlü FSM sentezi
- petri ağı
- aşağı itme otomat
- Kuantum sonlu otomatlar (QFA)
- tanınabilir dil
- SCXML
- yarı otomatik
- Yarı grup eylemi
- sıralı mantık
- Spesifikasyon ve Açıklama Dili
- Durum diyagramı
- durum kalıbı
- Senkronizasyon sırası
- Dönüşüm monoid
- geçiş monoid
- geçiş sistemi
- Ağaç otomatı
- Turing makinesi
- UML durum makinesi
- Benzersiz giriş/çıkış sırası (UIO)
Referanslar
daha fazla okuma
Genel
- Sakarovitch, Jacques (2009). Otomat teorisinin unsurları . Fransızcadan Reuben Thomas tarafından çevrilmiştir. Cambridge Üniversitesi Yayınları . ISBN'si 978-0-521-84425-3. Zbl 1188.68177 .
- Wagner, F., "Sonlu Durum Makineleri ile Modelleme Yazılımı: Pratik Bir Yaklaşım", Auerbach Publications, 2006, ISBN 0-8493-8086-3 .
- ITU-T, Tavsiye Z.100 Spesifikasyon ve Tanımlama Dili (SDL)
- Samek, M., Practical Statecharts in C/C++ , CMP Books, 2002, ISBN 1-57820-110-1 .
- Samek, M., Practical UML Statecharts in C/C++, 2. Baskı , Newnes, 2008, ISBN 0-7506-8706-1 .
- Gardner, T., İleri Durum Yönetimi , 2007
- Cassandras, C., Lafortune, S., "Ayrık Olay Sistemlerine Giriş". Kluwer, 1999, ISBN 0-7923-8609-4 .
- Timothy Kam, Sonlu Durum Makinelerinin Sentezi: Fonksiyonel Optimizasyon . Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
- Tiziano Villa, Sonlu Durum Makinelerinin Sentezi: Mantık Optimizasyonu . Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
- Carroll, J., Long, D., Biçimsel Dillere Giriş ile Sonlu Otomata Teorisi . Prentice Hall, Englewood Kayalıkları, 1989.
- Kohavi, Z., Anahtarlama ve Sonlu Otomata Teorisi . McGraw-Hill, 1978.
- Gill, A., Sonlu Durum Makineleri Teorisine Giriş . McGraw-Hill, 1962.
- Ginsburg, S., Matematiksel Makine Teorisine Giriş . Addison-Wesley, 1962.
Teorik bilgisayar biliminde sonlu durum makineleri (otomata teorisi)
- Arbib, Michael A. (1969). Soyut Otomatların Teorileri (1. baskı). Englewood Cliffs, NJ: Prentice-Hall, Inc. ISBN 978-0-13-913368-8.
- Bobrow, Leonard S.; Arbib, Michael A. (1974). Ayrık Matematik: Bilgisayar ve Bilgi Bilimi için Uygulamalı Cebir (1. baskı). Philadelphia: WB Saunders Company, Inc. ISBN 978-0-7216-1768-8.
- Booth, Taylor L. (1967). Sıralı Makineler ve Otomatlar Teorisi (1. baskı). New York: John Wiley and Sons, Inc. Library of Congress Card Katalog Numarası 67-25924.
- Boolo, George; Jeffrey, Richard (1999) [1989]. Hesaplanabilirlik ve Mantık (3. baskı). Cambridge, İngiltere: Cambridge University Press. ISBN'si 978-0-521-20402-6.
- Brookshear, J. Glenn (1989). Hesaplama Teorisi: Biçimsel Diller, Otomatlar ve Karmaşıklık . Redwood City, California: Benjamin/Cummings Publish Company, Inc. ISBN 978-0-8053-0143-4.
- Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Hesaplanabilirlik, Karmaşıklık ve Diller ve Mantık: Teorik Bilgisayar Biliminin Temelleri (2. baskı). San Diego: Academic Press, Harcourt, Brace & Company. ISBN'si 978-0-12-206382-4.
- Hopcroft, John; Ullman, Jeffrey (1979). Otomata Teorisine, Dillere ve Hesaplamaya Giriş (1. baskı). Kitle Okuma: Addison-Wesley. ISBN'si 978-0-201-02988-8.
- Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Otomata Teorisine, Dillere ve Hesaplamaya Giriş (2. baskı). Kitle Okuma: Addison-Wesley. ISBN'si 978-0-201-44124-6.
- Hopkin, David; Moss, Barbara (1976). Otomatlar . New York: Elsevier Kuzey Hollanda. ISBN'si 978-0-444-00249-5.
- Kozen, Dexter C. (1997). Otomatlar ve Hesaplanabilirlik (1. baskı). New York: Springer-Verlag. ISBN'si 978-0-387-94907-9.
- Lewis, Harry R. ; Papadimitriou, Christos H. (1998). Hesaplama Teorisinin Elemanları (2. baskı). Upper Saddle River, New Jersey: Prentice-Hall. ISBN'si 978-0-13-262478-7.
- Linz, Peter (2006). Resmi Diller ve Otomatlar (4. baskı). Sudbury, MA: Jones ve Bartlett. ISBN'si 978-0-7637-3798-6.
- Minsky, Marvin (1967). Hesaplama: Sonlu ve Sonsuz Makineler (1. baskı). New Jersey: Prentice Salonu.
- Papadimitriou, Hristos (1993). Hesaplamalı Karmaşıklık (1. baskı). Addison Wesley. ISBN'si 978-0-201-53082-7.
- Pippenger, Nicholas (1997). Hesaplanabilirlik Teorileri (1. baskı). Cambridge, İngiltere: Cambridge University Press. ISBN'si 978-0-521-55380-3.
- Rodger, Susan; Finley, Thomas (2006). JFLAP: Etkileşimli Biçimsel Diller ve Otomata Paketi (1. baskı). Sudbury, MA: Jones ve Bartlett. ISBN'si 978-0-7637-3834-1.
- Sipser, Michael (2006). Hesaplama Teorisine Giriş (2. baskı). Boston Kütlesi: Thomson Kurs Teknolojisi. ISBN'si 978-0-534-95097-2.
- Ahşap, Derin (1987). Hesaplama Teorisi (1. baskı). New York: Harper & Row, Publishers, Inc. ISBN 978-0-06-047208-5.
Teorik bilgisayar biliminde soyut durum makineleri
- Gurevich, Yuri (Temmuz 2000). "Sıralı Soyut Durum Makineleri Sıralı Algoritmaları Yakalar" (PDF) . Hesaplamalı Mantık Üzerine ACM İşlemleri . 1 (1): 77–111. CiteSeerX 10.1.1.146.3017 . doi : 10.1145/343369.343384 . S2CID 2031696 .
Sonlu durum algoritmalarını kullanarak makine öğrenimi
- Mitchell, Tom M. (1997). Makine Öğrenimi (1. baskı). New York: WCB/McGraw-Hill Şirketi. ISBN'si 978-0-07-042807-2.
Donanım mühendisliği: durum minimizasyonu ve sıralı devrelerin sentezi
- Booth, Taylor L. (1967). Sıralı Makineler ve Otomatlar Teorisi (1. baskı). New York: John Wiley and Sons, Inc. Library of Congress Card Katalog Numarası 67-25924.
- Booth, Taylor L. (1971). Dijital Ağlar ve Bilgisayar Sistemleri (1. baskı). New York: John Wiley ve Sons, Inc. ISBN 978-0-471-08840-0.
- McCluskey, EJ (1965). Anahtarlama Devreleri Teorisine Giriş (1. baskı). New York: McGraw-Hill Book Company, Inc. Library of Congress Kart Katalog Numarası 65-17394.
- Tepe, Fredrick J.; Peterson, Gerald R. (1965). Anahtarlama Devreleri Teorisine Giriş (1. baskı). New York: McGraw-Hill Kitap Şirketi. Kongre Kartı Katalog Numarası 65-17394 Kütüphanesi.
Sonlu Markov zinciri süreçleri
- "Bir düşünebilirler Markov zinciri bir süreç olarak devletler bir dizi üzerinden arkaya hareket eder ler 1 , s 2 , ..., s r . ... devlet ise s i eyaletin yanındaki durağı geçer s j ile olasılık p ij . Bu olasılıklar bir geçiş matrisi formunda sergilenebilir"(Kemeny (1959), s. 384)
Sonlu Markov zinciri süreçleri, sonlu tipte alt kaymalar olarak da bilinir .
- Booth, Taylor L. (1967). Sıralı Makineler ve Otomatlar Teorisi (1. baskı). New York: John Wiley and Sons, Inc. Library of Congress Card Katalog Numarası 67-25924.
- Kemeny, John G.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). Sonlu Matematiksel Yapılar (1. baskı). Englewood Cliffs, NJ: Prentice-Hall, Inc. Kongre Kartı Katalog Numarası 59-12841 Kütüphanesi. Bölüm 6 "Sonlu Markov Zincirleri".
Dış bağlantılar
- Sonlu Devlet Otomata at Curlie
- Bir Sonlu Durum Makinesi kullanarak Basit bir AI davranışını modelleme Video Oyunlarında kullanım örneği
- Sonlu Durum Makinelerinin Ücretsiz Çevrimiçi Hesaplama Sözlüğü açıklaması
- NIST Algoritmalar Sözlüğü ve Sonlu Durum Makinelerinin Veri Yapıları açıklaması
- Mealy, Moore, Harel ve UML durum makinelerinin teorik yönlerini karşılaştırarak durum makinesi türlerine kısa bir genel bakış .