Aplikasi praktis dari Mesin Hingga Negara

8

Saya mencari aplikasi praktis dari Mesin Hingga Negara seperti DFA, NFA, Moore, mesin Mealy ...

Akan sangat membantu jika seseorang menunjuk ke contoh dari Kernel Linux. Saya tahu bahwa DFA digunakan dalam pencocokan string seperti algoritma KMP.

Apa pentingnya mesin NFA, Moore dan Mealy?

reference-request automata finite-automata pengguna5507
sumber
Anda mungkin ingin memeriksa Teknik Listrik juga untuk mesin Moore / Mealy
Ran G.
1
Aku benci menjadi orang yang bertele-tele (baik-baik saja, aku suka menjadi orang tua) tetapi semua komputer nyata adalah mesin negara yang benar - benar terbatas. Automata pushdown, automata terbatas linier, dan mesin Turing adalah ketidakmungkinan fisik (secara praktis, tentu saja saya tidak dapat membuktikan bahwa tidak ada mesin Turing nyata yang melayang di angkasa di suatu tempat). Kita bahkan tidak dapat, secara praktis, membuat komputer yang dapat mengenali bahasa reguler yang sewenang-wenang.
Patrick87
Lihat juga ini dan pertanyaan ini di Theoretical Computer Science .
Raphael

Jawaban:

8

Setiap kali Anda melakukan pencarian (khususnya "pencarian pola") di editor / alat favorit Anda, polanya diterjemahkan ke dalam beberapa bentuk mesin keadaan terbatas, yang melakukan pencocokan.

Bagian analisis leksikal dari kompiler / juru bahasa Anda (ya, bahkan shell Anda) sekali lagi merupakan otomat terbatas yang cocok dengan kata kunci dan token lainnya yang dikenali oleh bahasa tersebut.

Mesin penjual otomatis adalah otomat terbatas yang menerima koin dari berbagai denominasi dan mengenali kapan jumlah yang benar telah dimasukkan (OK, mesin penjual otomatis saat ini mungkin memiliki CPU kecil di dalam melakukan penambahan, tetapi hasil akhirnya sama).

vonbrand
sumber
7

(konsep) DFA / NFA memiliki beberapa aplikasi di bidang kompiler dan dalam konstruksi parser. Mereka juga digunakan untuk mengidentifikasi string sesuai dengan ekspresi reguler (yaitu mencari "pola" di web atau melalui database)

Mesin Moore / Mealy, adalah DFA yang juga memiliki output pada setiap jam. Mereka memiliki banyak aplikasi. Bahkan, setiap CPU, komputer, ponsel, jam digital dan bahkan mesin cuci Anda memiliki semacam mesin negara terbatas di dalamnya, yang mengendalikannya.

Mungkin saya harus menjelaskannya: "komputer" apa pun pada dasarnya adalah mesin negara yang terbatas.

Ran G.
sumber
4

Salah satu aplikasi utama adalah pemodelan sistem. Pada dasarnya, sistem perangkat lunak sederhana dapat dimodelkan sebagai Mesin Hingga Negara. (Dengan perangkat lunak sederhana, maksud saya bahasa yang dapat diwakili menggunakan ekspresi reguler). Ada banyak sistem "sederhana" seperti itu, mesin penjual otomatis adalah contoh (seperti yang ditunjukkan vzn).

Dengan menemukan persimpangan dua mesin keadaan terbatas, Anda dapat merancang dengan sangat sederhana sistem bersamaan yang bertukar pesan misalnya. Sebagai contoh, lampu lalu lintas adalah sistem yang terdiri dari subsitus mutliple (lampu lalu lintas yang berbeda) yang bekerja secara bersamaan.

Lihatlah contoh-contoh ini: http://www.site.uottawa.ca/~bochmann/SEG-2106-2506/Notes/LTSA-examples/examples/

Anda harus memiliki penganalisis LTSA untuk menjalankan contoh-contoh ini. http://www.doc.ic.ac.uk/ltsa/

Dipotong
sumber
3

Inilah referensi online yang sangat bagus tentang FSM & teori terkait, 75p, dengan banyak diagram. memiliki banyak aplikasi setelah bagian teori tengah, dan juga dalam banyak latihan dengan aplikasi contoh mis. p485:

bab 12 Finite-State Machines oleh Keller, Harvey Mudd college, CS60 textbook / CS, pengantar abstraksi

aplikasi sangat beragam. misalnya dari buku:

  • klasifikasi angka
  • menonton dengan timer
  • mesin penjual otomatis
  • lampu lalulintas
  • pemindai kode batang
  • pompa gas

bagian 12.4 Konstruksi EE misalnya

  • elemen logika
  • kuantisasi jam
  • kunci kombinasi
  • sandal jepit
  • adders
  • register
  • bus / multiplexing

FSM juga digunakan dalam deteksi wicara untuk menemukan fonem , salah satu poin utama penerapan perpustakaan online yang luar biasa ini yang memiliki lebih banyak detail di halaman manual dan dokumentasi: AT&T online perpustakaan FSM . lihat bagian "Perpustakaan FSM dan Aplikasi Pemrosesan Wicara" (yang juga mencantumkan beberapa "aplikasi" abstrak / teoretis)

dll!

vzn
sumber
1

Saya menggunakan mesin negara saat menulis driver perangkat. Berhati-hatilah bahwa mesin negara besar dapat menjadi berat. Pertimbangkan untuk menggunakan set makro ini ( https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at ) ... dengan cara itu transisi menjadi sangat sederhana sehingga Anda tidak bahkan perlu diagram keadaan. Ini karena makro memungkinkan Anda menulis kode mesin status Anda seolah-olah kode terstruktur. Saya menulis Cisco Transceiver Library untuk Nexus 7000 menggunakan makro ini.

eddyq
sumber
0

Dalam praktiknya, Anda akan melihatnya secara eksplisit sebagai variabel status integer (biasanya disebut 'state') yang mewakili mesin state sangat kasar yang mewakili tindakan apa yang dapat dipanggil oleh pengguna objek. Biasanya enumerasi dengan nilai-nilai seperti: {tidak diinisialisasi, diinisialisasi, ..., dihentikan}. Mesin negara sering eksplisit ketika mem-parsing data, dan akan ditandai oleh pernyataan switch dalam loop sementara di mana di bagian atas loop, karakter berikutnya didapat. Secara khusus, jika parsing memiliki tata bahasa reguler, FSM yang tepat tanpa fitur lain sering digunakan. Jika Anda berada dalam bahasa yang mendukung panggilan ekor, FSM umumnya diperagakan dengan saling rekursi (yang dapat membuat kode dibaca seperti spesifikasi pseudocode yang sangat jelas). Fitur yang sangat berguna dari FSM adalah kemampuan untuk beroperasi secara bersamaan karena Anda hanya perlu mengingat keadaan saat ini, daripada seluruh tumpukan eksekusi. (Yaitu: konteks beralih antara jutaan instance mesin negara).

rampok
sumber