Sonlu durum makinesi: Revizyonlar arasındaki fark
| [kontrol edilmemiş revizyon] | [kontrol edilmemiş revizyon] |
İçerik silindi İçerik eklendi
k Bot değişikliği Ekleniyor: sk:Konečný automat |
k Bot değişikliği Değiştiriliyor: uk:Скінченний автомат; Kozmetik değişiklikler |
||
28. satır:
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 red edilir. Kural olarak girdiler için karakterler sembol olarak kullanılır, eylemler yoktur.
45. satır:
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 S<sub>1</sub>'in başlangıç durumu olduğunu ve içiçe çift halka sayesinde de yine S<sub>1</sub>'in kabul durum olduğunu anlayabiliyoruz. Bu şekilde ifadede bir sıfır geldiği zaman S<sub>2</sub>'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 uygulamarı 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"
[[Dosya:Fsm_mealy_model_door_control.jpg|thumb|350px|right|Şekil 4 Dönüştürücü SDM: Mealy model örneği]]
59. satı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ü sonlu durum makinası|olay güdümlü SDM]]
* [[sanal sonlu durum makinası|sanal SDM (SSDM)]]
* [[Otomata tabanlı programlama]]
== Dış bağlantılar ==
=== İngilizce ===
* [http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=finite+state+machine Description from the Free On-Line Dictionary of Computing]
* NIST Dictionary of Algorithms and Data Structures [http://www.nist.gov/dads/HTML/finiteStateMachine.html entry]
* [http://www.eventhelix.com/RealtimeMantra/HierarchicalStateMachine.htm Hierarchical State Machines]
* [http://www.intelliwizard.com Round-trip Engineering State Machines]
* [http://www.sccs.swarthmore.edu/users/06/adem/engin/e15/lab4/ Using state machines in practical applications]
* [http://osteele.com/tools/reanimator/?detectflash=false Flash based demonstration of Finite State Machines being used in regular expressions]
==Kaynaklar==▼
*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-4711-3772-3▼
▲== Kaynaklar ==
▲* 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.
[[Kategori:Formal dilleri]]
Satır 122 ⟶ 121:
[[sv:Ändlig automat]]
[[th:เครื่องสถานะจำกัด]]
[[uk:Скінченний автомат]]
[[zh:有限状态自动机]]
| |||