Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
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ı).
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
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 'dir, bu ifade ayrıca bir dilin kendisini kabul eden SDM olması durumunda düzenli bir dil olduğunu gösterir (Bkz. ).
- 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.
- 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ı).
- 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 verilebilir.
Yazılım uygulamaları
Aşağıdaki kavramlar sonlu durum makinalarıyla yazılım uygulaması üretmek için genellikle kullanılırlar:
Ayrıca bakınız
Dış bağlantılar
İngilizce
- Description from the Free On-Line Dictionary of Computing[]
- NIST Dictionary of Algorithms and Data Structures entry 7 Ekim 2007 tarihinde Wayback Machine sitesinde .
- Hierarchical State Machines 27 Eylül 2007 tarihinde Wayback Machine sitesinde .
Kaynakça
- Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, .
- Samek, M., "Practical Statecharts in C/C++", CMP Books, 2002, .
- Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, .
- Timothy Kam, Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997,
- Tiziano Villa, Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997,
- 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.
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Sonlu durum makinasi veya sonlu durum otomati veya basitce durum makinasi sinirli sayida durumdan durumlar arasi gecislerden ve eylemlerin birlesmesiyle olusan davranislarin bir modelidir Sekil 1 Sonlu durum makinasiKavramlarDurum gecmis hakkinda bilgi saklar ornegin baslangictan su anki duruma kadar girdi degisimlerini gosterir Gecis durum degisimini gosterir ve gecisi saglamak icin yapilmasi gereken kosulla tanimlanir Eylem belirli bir zamanda gerceklestirilen etkinligin tanimidir Bircok eylem tipi vardir Giris eylemi Bu eylem duruma gecerken gerceklestirilir Cikis eylemi Bu eylem durumdan cikarken gerceklestirilir Girdi eylemi Mevcut duruma ve girdi kosullarina bagli gerceklestirilen eylemdir Gecis eylemi Belirli bir gecis gerceklestirilirken olusan eylemdir SDM durum cizgeleriyle veya gecis cizgeleriyle temsil edilir Bkz Sekil 1 Bunun disinda cok sayida durum gecis tablo tipleri kullanilmaktadir En cok karsilasilan temsil asagida gosterilmistir mevcut durum B de iken kosul Y gerceklestiginde sonraki durum C ortaya cikar Tum eylemlerin bilgisi ancak dipnot kullanimiyla eklenebilmektedir Tum eylemlerin bilgisini iceren bir SDM tanimi durum tablolarini kullanarak mumkundur Bkz Sanal Sonlu Durum Makinasi Durum Gecis Tablosu Mevcut Durum Kosul Durum A Durum B Durum CKosul X Kosul Y Durum C Kosul Z Burada gosterilen tepkisel sistemleri modellemeye ek olarak sonlu durum makinalari cok farkli alanda onemlidir bu alanlar elektrik muhendisligi dilbilim bilgisayar bilimleri felsefe biyoloji matematik ve mantik olarak sayilabilir Sonlu durum makinalari otomata teorisi ve hesaplama teorisinde calisilan otomatlarin bir sinifidir Bilgisayar bilimlerinde sonlu durum makinalari uygulama davranisi donanim sayisal sistemlerinin tasarimi yazilim muhendisligi ag protokolleri ve hesaplama ve dillerin ogretilmesinde genis olcude kullanilmaktadir SiniflandirmaAlici Acceptor Taniyici Recognizer ve donusturucu Transducer olmak uzere iki farkli grup vardir Alicilar Taniyicilar Alicilar ve taniyicilar girdinin makina tarafindan kabul edilip edilmedigini belirten evet hayir 0 veya 1 ikili cikti cevaplarindan birini verirler SDM nin tum durumlarinin kabul eden veya kabul etmeyen olmasi gerekir Girdiler islenirken mevcut durum kabul eden bir durumsa girdi kabul edilir kabul etmeyen bir durumsa girdi reddedilir Kural olarak girdiler icin karakterler sembol olarak kullanilir eylemler yoktur Makina ayrica makinenin kabul ettigi tum kelimeleri iceren makinenin reddettigi tum kelimeleri icermeyen dil olarak tanimlanabilir Tanim geregi SDM ler tarafindan kabul edilen diller dir bu ifade ayrica bir dilin kendisini kabul eden SDM olmasi durumunda duzenli bir dil oldugunu gosterir Bkz Baslangic durumu Baslangici gosteren ve Start ifadesiyle veya hicbir yerden gelen bir okla gosterilen durumdur Kabul durumu Makinanin yordamini basariyla gerceklestirdigi durumdur Cift halka ile temsil edilir Yordamin bitisini gosterir Yukaridaki sekilde cift sayida sifir iceren ikili ifadeleri olusturan deterministik sonlu otomata ornegi gorulmektedir Soldan gelen ok sayesinde S1 in baslangic durumu oldugunu ve ic ice cift halka sayesinde de yine S1 in kabul durum oldugunu anlayabiliyoruz Bu sekilde ifadede bir sifir geldigi zaman S2 e gecerek ek olarak mutlaka bir sifir daha eklenecegi garantilenmis oluyor ve her zaman kabul edilen ifade cift sayida sifir iceriyor Donusturuculer Donusturuculer verilen girdi ve eylemleri kullanarak ortaya cikan durumlara dayanarak cikti uretirler Kontrol uygulamalari icin kullanilirlar Iki farkli tipi asagida anlatilmaktadir SDM sadece giris eylemlerini kullanir cikis duruma baglidir Moore modelinin avantaji davranisin basitlesmesidir Sekil 3 asansor kapisi Moore SDM sini gostermektedir Durum makinasi iki komutu tanimaktadir command open ve command close ve bu komutlar durum gecislerini tetikler Opening durumunda girdi eylemi E kapiyi acan bir motoru baslatir Closing durumundaki girdi eylemi ise motoru kapiyi kapatma yonunde calistirir Opened ve Closed durumlari herhangi bir eylem gerceklestirmez Dis dunyaya ornegin diger durum makinalarina vaziyeti bildirirler door is open kapi acik veya door is closed kapi kapali Sekil 4 Donusturucu SDM Mealy model ornegiSDM sadece girdi eylemlerini kullanir cikti girdi ve duruma baglidir Mealy SDM lerinin kullanimi durum sayisinin azalmasini saglamaktadir Sekil 4 teki ornek Sekil 3 teki Moore makinasiyla ayni isi yapan Mealy makinasini gostermektedir Iki girdi eylemi vardir I command close gelirse kapiyi kapatmak icin motoru baslat ve command open gelirse kapiyi acmak icin motoru diger yonde baslat Pratikte bu iki modelin karisimlari kullanilmaktadir Ayrica deterministik DFA ve deterministik olmayan NDFA ayrimi vardir Deterministik otomatada her durum icin olasi her girdiye karsilik gelen bir gecis vardir Deterministik olmayan otomatada bir durumdan bir girdi icin hic bir veya daha fazla gecis olabilmektedir Bu ayrim pratikte anlamlidir ancak teoride NDFA yi esit bir DFA ya donusturen bir algoritma olmasi bu donusum her ne kadar otomatanin karmasikligini artirsa da dolayisiyla onemsizdir GerceklestirimDonanim uygulamalari Sonlu durum makinalari sayisal devrelerde programlanabilir mantik cihazi programlanabilir mantik kontrolcusu mantik kapilari ve Flip floplar veya anahtarlar kullanilarak gerceklestirilebilir Daha belirgin olursak donanim gerceklestirimi durum degiskenlerini saklamak icin islemci yazmaci durum gecisine karar veren kombinasyonel mantik bloku ve SDM nin ciktisina karar veren baska bir kombinasyonel mantik blokuna ihtiyac duyulur Klasik donanim gerceklestirimlerine ornek olarak verilebilir Yazilim uygulamalari Asagidaki kavramlar sonlu durum makinalariyla yazilim uygulamasi uretmek icin genellikle kullanilirlar Ayrica bakinizAlgoritmik durum makinesi Turing makinesiDis baglantilarIngilizce Description from the Free On Line Dictionary of Computing olu kirik baglanti NIST Dictionary of Algorithms and Data Structures entry 7 Ekim 2007 tarihinde Wayback Machine sitesinde Hierarchical State Machines 27 Eylul 2007 tarihinde Wayback Machine sitesinde KaynakcaWagner 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