Apa perbedaan antara mesin automata terbatas dan mesin negara terbatas?

16

Saya telah menggunakan FSM dalam desain Sirkuit berurutan Digital. Tapi saya tidak terbiasa dengan Finite Automata. Adakah yang bisa membantu saya memahami perbedaan 'dasar' di antara keduanya?

terminology automata finite-automata gpuguy
sumber
5
Dari Wikipedia : "... Dalam teori automata, cabang ilmu komputer teoritis, sebuah deterministic finite automaton (DFA) - juga dikenal sebagai mesin keadaan terbatas deterministik - adalah mesin keadaan terbatas yang menerima / menolak rangkaian simbol hingga dan hanya menghasilkan simbol perhitungan unik (atau lari) dari otomat untuk setiap string masukan ... ". DFA adalah istilah yang disukai yang digunakan dalam teori automata, FSM adalah istilah yang disukai yang digunakan dalam aplikasi praktis.
Vor
4
Saya pikir FSM lebih inklusif, termasuk juga Mealy dan Moore automata. NFA adalah satu model spesifik.
Raphael
@ Raphael: Saya setuju dengan Anda, FSM tampak lebih luas (bahkan wikipedia membuat perbedaan antara Transduser, Akseptor, Klasifikasi dan Sequencer). "DFA" ~ "FSM acceptors" (FSM dengan hanya output ya / tidak) ... selanjutnya FSM dalam desain sirkuit, biasanya menggunakan output ... Mungkin Anda dapat mengubah komentar Anda menjadi sebuah jawaban.
Vor
Secara pribadi, saya menggunakan FSM sebagai istilah luas yang mencakup mesin DFA, NFA, Mealy dan Moore, transduser (finite-state) dll; sederhananya semuanya dengan ruang keadaan terbatas dan tanpa memori tambahan.
Dan
1
@Raphael In dalam teori formal (atau teori perhitungan) kami lebih suka menggunakan kata "Automata" - untuk menekankan bahwa mesin kami adalah mesin 'otomatis' (bergerak sendiri - seperti komputer Anda) - "otomatis" dalam arti bahwa sekali Anda telah menetapkan aturan transisi, Anda tidak perlu menerapkan kecerdasan eksplisit apa pun untuk memproses / mengklasifikasikan string (Anda hanya perlu merujuk aturan transisi pada setiap langkah). - sedangkan istilah mesin lebih disukai dalam konteks perangkat (daripada model) - meskipun keduanya sinonim satu sama lain.
Grijesh Chauhan

Jawaban:

12

Sejauh yang saya mengerti, keduanya memiliki "status", dan "tindakan" yang membuat mesin bergerak dari satu kondisi ke kondisi lain menggunakan sinyal input. Jadi ide-ide konseptualnya sama. Ada beberapa perbedaan dalam detailnya.

Dalam FSM untuk desain rangkaian, sinyal input sebagian besar dianggap sedikit (biner), sedangkan dalam keadaan terbatas automata seseorang dapat memiliki alfabet "abstrak" simbol input yang umum. Kedua, FSM juga menghasilkan output, terkait dengan keadaan yang dicapai, juga biner. Dalam terminologi automata 'ekstensi' ini disebut mesin Moore. Automata memiliki status akhir (atau menerima), yang menandakan input yang baik dibaca. Akhirnya, FSM sebagian besar deterministik, yaitu, untuk setiap input dalam keadaan tertentu ada satu keadaan berikutnya. Dalam teori automata seseorang juga mempertimbangkan varian nondeterministik di mana orang mungkin memiliki pilihan di mana harus pindah.

Hendrik Jan
sumber
6

Berdasarkan pengalaman saya serta artikel Wikipedia, ada beberapa jenis mesin negara yang terbatas , termasuk

Beberapa gagasan terbang di sekitar berbeda dalam motivasi; beberapa muncul dari teori bahasa dan / atau komputasi, yang lain dari arsitektur komputer.

Perhatikan bahwa Anda juga dapat mengubah beberapa paradigma untuk mendapatkan automata yang, bisa dibilang, automata keadaan terbatas, misalnya

Seperti yang Anda lihat, vanilla automata terbatas seperti yang diajarkan dalam TCS 101 hanyalah satu dari banyak rasa, masing-masing dengan definisi mereka sendiri (kurang lebih formal).

Raphael
sumber
2

Meskipun ide utama yang mereka berdua andalkan adalah sama. Keduanya menggunakan status terbatas dan melompat ke status lain sebagai umpan input. Namun, FSM menjadi mesin, seperti Full adder atau SR flipflop memiliki bit sebagai input dan output. Ya, FSA juga memiliki bit output, 0 untuk non-terminating state dan 1 untuk terminating state, tetapi ini adalah mekanisme abstrak dan tidak terlihat. Ada perbedaan dalam digraf yang ditarik untuk mewakili mereka. Selain itu FSA adalah perangkat logis dan komputasi sedangkan FSM adalah perangkat logika digital.

Saryan Sandeep
sumber