Sonlu durum makinesi - Finite-state machine

Combinational logic Finite-state machine Pushdown automaton Turing machine Automata theoryOtomat teorisi.svg
Bu resim hakkında
Otomat sınıfları
(Her katmana tıklamak, o konuyla ilgili bir makale alır)

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

Turnike için durum şeması
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

Şekil 1 UML durum tablosu örneği (bir ekmek kızartma makinesi fırını)
Şekil 2 SDL durum makinesi örneği
Şekil 3 Basit bir sonlu durum makinesi örneği

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

Durum geçiş tablosu
  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

Şekil 4: Alıcı FSM: "nice" dizesinin ayrıştırılması.
Şekil 5: Bir alıcının temsili; bir ikili sayı 0 ların eşit sayıda sahip olup olmadığını saptamaktadır, bu örnekte gösterildiği bir S 1 bir olduğunu kabul durumu ve S 2 a, durum kabul olmayan .

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

Şekil 6 Dönüştürücü FSM: Moore model örneği
Şekil 7 Dönüştürücü FSM: Mealy model örneği

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ı

Şekil 9 Bir tür durum makinesi olan 4 bitlik bir TTL sayacının devre şeması

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:

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

Referanslar

daha fazla okuma

Genel

Teorik bilgisayar biliminde sonlu durum makineleri (otomata teorisi)

Teorik bilgisayar biliminde soyut durum makineleri

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