Apa pencerahan yang seharusnya saya dapatkan setelah mempelajari automata terbatas?

Saya telah merevisi Teori Komputasi untuk bersenang-senang dan pertanyaan ini telah mengganggu saya untuk sementara waktu (lucu tidak pernah memikirkannya ketika saya belajar Teori Automata di sarjana saya). Jadi "mengapa" tepatnya kita mempelajari automata terbatas deterministik dan non-deterministik (DFA / NFA)? Jadi, inilah beberapa jawaban yang saya dapatkan setelah soliloquing tetapi masih gagal melihat kontribusi keseluruhan mereka pada momen 'aha':

1. Untuk mempelajari apa mereka dan tidak mampu yaitu keterbatasan
   • Mengapa?
2. Karena mereka adalah model dasar perhitungan teoretis dan akan meletakkan dasar model komputasi yang lebih mampu lainnya.
   • Apa yang membuat mereka 'dasar'? Apakah mereka hanya memiliki sedikit penyimpanan dan transisi status?
3. Oke, lalu bagaimana? Bagaimana semua ini berkontribusi untuk menjawab pertanyaan tentang komputabilitas? Tampaknya mesin Turing membantu memahami hal ini dengan sangat baik dan ada model perhitungan yang lebih rendah seperti PDA, DFA / NFAs / Regexes dll. Tetapi jika seseorang tidak tahu FAs apa yang mereka lewatkan?

Jadi meskipun saya 'mengerti' sampai batas tertentu, saya tidak dapat menjawab pertanyaan ini untuk diri saya sendiri? Bagaimana sebaiknya Anda menjelaskan 'mengapa belajar D / N-FA'? Apa pertanyaan yang ingin mereka jawab? Bagaimana ini membantu dan mengapa hal itu diajarkan pertama kali dalam Teori Automata?

PS: Saya mengetahui berbagai aplikasi leksikografis dan pencocokan pola yang dapat diimplementasikan. Namun, saya tidak ingin tahu apa yang bisa digunakan untuk praktis tetapi apa alasan mereka untuk menggunakan / penemuan / desain selama kulminasi mempelajari teori perhitungan. Secara historis berbicara apa yang menyebabkan seseorang memulai dengan ini dan apa pengertian 'aha' yang seharusnya dituju? Jika Anda menjelaskan pentingnya mereka kepada siswa CS yang baru mulai mempelajari Teori Automata, bagaimana Anda melakukannya?

Saya pribadi telah menikmati beberapa Aha! beberapa saat dari mempelajari teori automata dasar. NFA dan DFA membentuk mikrokosmos untuk ilmu komputer teoretis secara keseluruhan.

1. Apakah Non-determinisme Mengarah ke Efisiensi? Ada contoh standar di mana otomat deterministik minimal untuk suatu bahasa secara eksponensial lebih besar daripada otomat non-deterministik minimal. Memahami perbedaan ini untuk mesin Turing adalah inti dari ilmu komputer (teoritis). NFA dan DFA memberikan contoh paling sederhana yang saya tahu di mana Anda dapat secara eksplisit melihat kesenjangan ketat antara determinisme dan non-determinisme.
2. Komputasi! = Kompleksitas. NFA dan DFA keduanya mewakili bahasa reguler dan setara dalam apa yang mereka hitung. Mereka berbeda dalam cara mereka menghitung.
3. Mesin Perbaiki Bahasa. Ini adalah pandangan berbeda tentang apa yang kami hitung dan bagaimana kami menghitung. Anda dapat menganggap bahasa yang dapat dikomputasi (dan fungsi) sebagai mendefinisikan kelas ekuivalensi automata. Ini adalah perubahan perspektif mendasar dalam TCS, di mana kami fokus tidak hanya pada apa, tetapi bagaimana cara menghitung dan mencoba untuk memilih 'bagaimana' yang tepat ketika merancang suatu algoritma atau memahami ruang berbagai cara dalam mempelajari kelas kompleksitas.
4. Nilai Representasi Canonical. DFA adalah contoh klasik dari suatu struktur data yang menerima representasi kanonik. Setiap bahasa reguler memiliki DFA minimal yang unik. Ini berarti bahwa mengingat DFA minimal, operasi penting seperti penyertaan bahasa, pelengkap, dan pengecekan penerimaan suatu kata menjadi sepele. Merancang dan mengeksploitasi representasi kanonik adalah trik yang berguna ketika mengembangkan algoritma.
5. Absennya Representasi Kanonik. Tidak ada representasi kanonik dari ekspresi reguler atau NFA yang diterima dengan baik. Jadi, terlepas dari poin di atas, representasi kanonik tidak selalu ada. Anda akan melihat poin ini di berbagai bidang dalam ilmu komputer. (misalnya, rumus logika proposisional juga tidak memiliki representasi kanonik, sementara ROBDD melakukannya).
6. Biaya Representasi Canonical. Anda bahkan dapat memahami perbedaan antara NFA dan DFA sebagai teorema tanpa-makan siang algoritmik . Jika kami ingin memeriksa inklusi bahasa di antara, atau melengkapi NFA, Anda dapat menentukan dan menguranginya dan melanjutkan dari sana. Namun, operasi "reduksi" ini berbayar. Anda akan melihat contoh kanonisasi dengan biaya di beberapa bidang ilmu komputer lainnya.
7. Tak Terbatas! = Tidak Diputuskan. Kesalahpahaman yang umum adalah bahwa masalah yang bersifat infinitary pada dasarnya tidak dapat diputuskan. Bahasa reguler mengandung banyak sekali string dan memiliki beberapa properti yang dapat ditentukan. Teori bahasa reguler menunjukkan kepada Anda bahwa tak terhingga saja bukanlah sumber ketidakpastian.
8. Tahan Infinity di Telapak Automaton Anda. Anda dapat melihat robot hingga murni sebagai struktur data untuk mewakili set yang tak terbatas. ROBDD adalah struktur data untuk merepresentasikan fungsi Boolean, yang dapat Anda pahami sebagai representasi set yang terbatas. Otot-terbatas adalah ekstensi ROBDD yang tak terbatas dan alami.
9. Prosesor yang Rendah Hati. Prosesor modern memiliki banyak hal di dalamnya, tetapi Anda dapat memahaminya sebagai otomat terbatas. Hanya kesadaran ini yang membuat arsitektur komputer dan desain prosesor jauh lebih tidak menakutkan bagi saya. Ini juga menunjukkan bahwa, dalam praktiknya, jika Anda menyusun dan memanipulasi keadaan Anda dengan hati-hati, Anda bisa menjadi sangat jauh dengan automata terbatas.
10. Perspektif Aljabar. Bahasa reguler membentuk monoid sintaksis dan dapat dipelajari dari perspektif itu. Lebih umum, Anda dapat dalam studi selanjutnya juga bertanya, apa struktur aljabar yang tepat sesuai dengan beberapa masalah komputasi.
11. Perspektif Kombinatorial. Finite-automaton adalah grafik berlabel. Memeriksa apakah suatu kata diterima mengurangi untuk menemukan jalur dalam grafik berlabel. Jumlah algoritma Automata ke transformasi grafik. Memahami struktur automata untuk berbagai sub-keluarga bahasa reguler adalah area penelitian aktif.
12. Segitiga cinta Aljabar-Bahasa-Kombinatorik. Teorema Myhill-Nerode memungkinkan Anda untuk memulai dengan bahasa dan menghasilkan otomat atau monoid sintaksis. Secara matematis, kami memperoleh terjemahan antara berbagai jenis objek matematika. Berguna untuk mengingat terjemahan-terjemahan tersebut dan mencari di bidang ilmu komputer lainnya, dan untuk bergerak di antara mereka tergantung pada aplikasi Anda.
13. Matematika adalah Bahasa Gambar Besar. Bahasa reguler dapat dikarakterisasi dengan NFA (grafik), ekspresi reguler (tata bahasa formal), mesin Turing (mesin) read-only, mono sintaksis (aljabar), aljabar Kleene (aljabar), logika orde dua monadik, dll. Yang lebih umum Fenomena yang penting, konsep abadi memiliki banyak karakterisasi matematika yang berbeda, masing-masing membawa rasa yang berbeda untuk pemahaman kita tentang ide tersebut.
14. Lemmas untuk Matematika yang Bekerja. Pumping Lemma adalah contoh yang bagus dari alat teoretis yang dapat Anda manfaatkan untuk memecahkan masalah yang berbeda. Bekerja dengan Lemmas adalah praktik yang baik untuk mencoba membangun hasil yang ada.
15. Diperlukan! = Cukup. Teorema Myhill-Nerode memberi Anda kondisi yang diperlukan dan memadai untuk suatu bahasa menjadi teratur. Pumping Lemma memberi kita kondisi yang diperlukan. Membandingkan keduanya dan menggunakannya dalam situasi yang berbeda membantu saya memahami perbedaan antara kondisi yang diperlukan dan cukup dalam praktik matematika. Saya juga belajar bahwa kondisi yang diperlukan dan cukup dapat digunakan kembali adalah sebuah kemewahan.
16. Perspektif Bahasa Pemrograman. Ekspresi reguler adalah contoh sederhana dan indah dari bahasa pemrograman. Dalam penggabungan, Anda memiliki analog komposisi berurutan dan di bintang Kleene, Anda memiliki analog iterasi. Dalam mendefinisikan sintaks dan semantik ekspresi reguler, Anda membuat langkah kecil ke arah teori bahasa pemrograman dengan melihat definisi induktif dan semantik komposisi.
17. Perspektif Penyusun. Terjemahan dari ekspresi reguler ke otomat terbatas juga merupakan penyusun teoretis yang sederhana. Anda dapat melihat perbedaan antara penguraian, pembuatan kode menengah, dan optimisasi kompiler, karena perbedaan dalam membaca ekspresi reguler, menghasilkan automaton, dan kemudian meminimalkan / menentukan automaton.
18. Kekuatan Iterasi. Dalam melihat apa yang dapat Anda lakukan dalam otomat-terbatas dengan loop dan satu tanpa, Anda dapat menghargai kekuatan iterasi. Ini dapat membantu memahami perbedaan antara sirkuit dan mesin, atau antara logika klasik dan logika titik tetap.
19. Aljabar dan Batubara. Bahasa reguler membentuk monoid sintaksis, yang merupakan struktur aljabar. Bentuk automata terbatas yang dalam bahasa teori kategori disebut sebagai coalgebra. Dalam kasus otomat deterministik, kita dapat dengan mudah bergerak di antara representasi aljabar dan coalgebra, tetapi dalam kasus NFA, ini tidak begitu mudah.
20. Perspektif Aritmatika. Ada hubungan yang mendalam antara perhitungan dan teori bilangan. Anda dapat memilih untuk memahami ini sebagai pernyataan tentang kekuatan teori bilangan, dan / atau universalitas perhitungan. Anda biasanya tahu bahwa automata terbatas dapat mengenali jumlah simbol yang genap, dan mereka tidak dapat menghitung cukup untuk mencocokkan tanda kurung. Tetapi berapa banyak aritmatika yang mereka mampu? Automata yang terbatas dapat memutuskan rumus aritmatika Presburger. Prosedur keputusan paling sederhana yang saya tahu untuk aritmatika Presburger mengurangi formula menjadi otomat. Ini adalah satu sekilas dari mana Anda dapat maju ke masalah 10 Hilbert dan resolusi itu yang mengarah pada penemuan koneksi antara persamaan Diophantine dan mesin Turing.
21. Perspektif Logis. Komputasi dapat dipahami dari perspektif yang murni logis. Automata terbatas dapat dicirikan oleh logika urutan kedua monadik lemah atas kata-kata terbatas. Ini adalah contoh favorit saya, non-sepele dari karakterisasi logis perangkat komputasi. Teori kompleksitas deskriptif menunjukkan bahwa banyak kelas kompleksitas memiliki karakterisasi yang murni logis juga.
22. Automata Hingga Bersembunyi di Tempat yang Tidak Pernah Anda Bayangkan. (Hat-tip untuk komentar Martin Berger tentang kaitannya dengan teori pengkodean). Hadiah Nobel Kimia 2011 diberikan untuk penemuan kristal semu. Matematika di balik kristal semu terhubung ke tilt aperiodik. Salah satu ubin aperiodik khusus pada bidang ini disebut Ubin Cartwheel, yang terdiri dari bentuk layang-layang dan bentuk dasi kupu-kupu. Anda bisa menyandikan bentuk-bentuk ini dalam bentuk 0s dan 1s dan kemudian mempelajari properti dari sekuens ini, yang mengkodekan urutan pola. Faktanya, jika Anda memetakan 0 hingga 01 dan 1 hingga 0, dan berulang kali menerapkan peta ini ke angka 0, Anda akan mendapatkan, 0, 01, 010, 01001, dll. Perhatikan bahwa panjang string ini mengikuti urutan Fibonacci. Kata-kata yang dihasilkan dengan cara ini disebut kata Fibonacci. Urutan bentuk tertentu yang diamati dalam Penrose tilings dapat dikodekan sebagai kata Fibonacci. Kata-kata seperti itu telah dipelajari dari sudut pandang teori otomat, dan coba tebak, beberapa keluarga kata diterima oleh automata terbatas, dan bahkan memberikan contoh perilaku terburuk untuk algoritma standar seperti algoritma minimisasi Hopcroft. Tolong beritahu saya bahwa Anda pusing.

Saya dapat melanjutkan. (Dan terus.) * Saya merasa berguna memiliki automata di belakang kepala saya dan mengingatnya setiap sekarang dan kemudian untuk memahami konsep baru atau untuk mendapatkan intuisi tentang ide-ide matematika tingkat tinggi. Saya ragu bahwa semua yang saya sebutkan di atas dapat dikomunikasikan dalam beberapa kuliah pertama kursus, atau bahkan dalam kursus pertama. Ini adalah imbalan jangka panjang berdasarkan investasi awal yang dibuat dalam kuliah awal kursus teori automata.

Untuk membahas judul Anda: Saya tidak selalu mencari pencerahan, tetapi ketika saya melakukannya, saya lebih suka automata terbatas. Tetap haus, teman saya.

Ada banyak alasan teoritis yang baik untuk mempelajari N / DFA. Dua yang langsung muncul di pikiran adalah:

1. Mesin Turing (menurut kami) menangkap semua yang dapat dihitung. Namun, kita dapat bertanya: Bagian mana dari mesin Turing yang "penting"? Apa yang terjadi ketika Anda membatasi mesin Turing dengan berbagai cara? DFA adalah batasan yang sangat parah dan alami (menghilangkan ingatan). PDA adalah batasan yang tidak terlalu parah, dll. Secara teoritis menarik untuk melihat apa yang memberi Anda memori dan apa yang terjadi ketika Anda pergi tanpa itu. Sepertinya pertanyaan yang sangat wajar dan mendasar bagi saya.

2. Mesin Turing membutuhkan pita tak terbatas. Alam semesta kita terbatas, jadi dalam beberapa hal setiap perangkat komputasi adalah DFA. Sepertinya topik yang penting, dan sekali lagi alami, untuk dipelajari.

Bertanya mengapa seseorang harus mempelajari DFA sama dengan menanyakan mengapa seseorang harus mempelajari teorema kelengkapan Godel ketika hal yang benar-benar menarik adalah teorema ketidaklengkapannya .

Alasan mereka menjadi topik pertama dalam teori automata adalah karena itu wajar untuk membangun ke mode yang lebih rumit dari yang kurang rumit.

Untuk menambahkan satu perspektif lagi ke sisa jawaban: karena Anda benar-benar dapat melakukan hal-hal dengan automata terbatas, berbeda dengan mesin Turing.

Hampir semua properti menarik dari mesin Turing tidak dapat diputuskan. Sebaliknya, dengan automata terbatas, hanya tentang segala sesuatu adalah decidable. Kesetaraan bahasa, inklusi, kekosongan, dan universalitas semuanya dapat dipilih. Dikombinasikan dengan automata terbatas ditutup di bawah hampir setiap operasi yang dapat Anda pikirkan, dan bahwa operasi ini dapat dihitung, Anda dapat melakukan hampir semua hal yang ingin Anda lakukan dengan automata terbatas.

Ini berarti bahwa jika Anda dapat menangkap sesuatu menggunakan automata terbatas, Anda secara otomatis mendapatkan banyak alat untuk menganalisisnya. Misalnya, dalam pengujian perangkat lunak, sistem dan spesifikasinya dapat dimodelkan sebagai automata terbatas. Anda kemudian dapat secara otomatis menguji apakah sistem Anda mengimplementasikan spesifikasi dengan benar.

Oleh karena itu, mesin Turing dan automata terbatas mengajarkan kepada orang-orang suatu kontras yang menarik dan ada di mana-mana: kekuatan yang lebih deskriptif berjalan seiring dengan lebih sedikit kemudahan penelusuran. Automata yang terbatas tidak dapat menjelaskan banyak hal, tetapi setidaknya kita dapat melakukan hal-hal dengan mereka.

Negara. Anda perlu belajar bahwa seseorang dapat memodelkan dunia (untuk masalah-masalah tertentu) sebagai ruang keadaan terbatas, dan seseorang dapat berpikir tentang perhitungan dalam pengaturan ini. Ini adalah wawasan yang sederhana tetapi sangat berguna jika Anda melakukan pemrograman apa pun - Anda akan mengalami keadaan berulang-ulang, dan FA memberi Anda cara untuk memikirkannya. Saya menganggap ini sebagai alasan yang cukup untuk mengajar kelas yang lengkap. Tentu saja, negara dapat bersifat deterministik atau non-deterministik. Dengan demikian DFA dan NFA, tetapi Anda dapat mengkonversi di antara mereka, dll.

Hal kedua yang harus dipelajari adalah teorema Menghentikan. Yang terkait dengan teorema ketidaklengkapan Godel. (Anda tidak dapat membangun mesin yang dapat menghitung semuanya, dan ada klaim matematis bahwa Anda tidak dapat membuktikan atau menyangkal, dan karena itu perlu dianggap sebagai aksioma. Artinya, kita hidup di dunia yang tidak memiliki deskripsi hingga atau nyata oracle - ya untuk kita!)

Sekarang, saya melakukan sarjana saya dalam matematika, dan Anda terbiasa dengan gagasan bahwa Anda belajar hal-hal yang Anda tidak tahu mengapa Anda belajar (teori grup, teori ukuran, teori himpunan, ruang Hilbert, dll, dll, dll. [Semua hal yang baik , BTW]). Ada sesuatu yang bisa dikatakan tentang belajar cara belajar - lain kali Anda harus belajar matematika bizarro (karena Anda perlu menggunakannya untuk melakukan sesuatu di luar sana di dunia nyata) yang terlihat sangat aneh Anda ambil dengan tenang. Secara khusus, hal ketiga yang harus dipelajari adalah kematangan matematika - bisa berdebat dengan hati-hati tentang hal-hal, tahu kapan bukti benar atau tidak, tuliskan bukti, dll. Jika sudah memilikinya, kursus ini mudah, dan Anda tidak akan terlalu peduli banyak alasan Anda mempelajarinya.

Kecuali untuk ini, kursus ini hanya membuang-buang waktu Anda, seperti yang lainnya. Secara khusus, Anda dapat menjalani kehidupan yang bahagia tanpa mengetahui hal-hal ini. Tetapi ini benar-benar berlaku untuk semua pengetahuan. Lebih atau kurang. Bagi saya, mata kuliah di universitas layak dilakukan, jika Anda memandang dunia secara berbeda setelah mempelajarinya. Ini jelas merupakan salah satu kursus yang mengubah cara saya berpikir tentang dunia. Apa lagi yang bisa Anda tanyakan?

Meskipun sebenarnya bukan alasan mereka awalnya dipelajari, automata terbatas dan bahasa reguler yang mereka kenali cukup traktat sehingga mereka telah digunakan sebagai blok bangunan untuk teori matematika yang lebih rumit. Dalam konteks ini lihat terutama grup otomatis (grup di mana elemen dapat diwakili oleh string dalam bahasa reguler dan di mana produk elemen oleh generator grup dapat dihitung dengan transduser keadaan terbatas) dan subshift lunak (subshift dari ruang shift yang kata-kata terlarang membentuk bahasa biasa). Jadi ada alasan untuk mempelajarinya bahkan jika Anda tertarik pada matematika murni daripada ilmu komputer.

Automata terbatas juga telah digunakan dalam desain algoritma untuk objek jenis lain. Sebagai contoh, suatu algoritma Culik untuk menguji apakah otomat seluler satu dimensi dapat dibalikkan melibatkan pembuatan, modifikasi, dan pengujian properti NFA tertentu. Dan makalah FOCS tahun 1986 oleh Natarajan menunjukkan bagaimana memecahkan masalah tertentu dalam desain jalur perakitan mekanis dengan mereduksinya menjadi perhitungan tentang automata terbatas.

Anda mengajukan (setidaknya) dua pertanyaan yang berbeda: (a) Apa bagian dari teori yang dibangun di atas automata terbatas saat ini? (B) Mengapa automata terbatas dikembangkan di tempat pertama? Saya pikir cara terbaik untuk mengatasi yang terakhir adalah dengan melihat koran lama, seperti:

• Rabin, Scott, Finite Automata dan Masalah Keputusannya , 1959

Inilah dua paragraf pertama:

Mesin Turing secara luas dianggap sebagai prototipe abstrak dari komputer digital; Namun, para pekerja di lapangan semakin merasa bahwa gagasan tentang mesin Turing terlalu umum untuk dijadikan model akurat komputer yang sebenarnya. Telah diketahui dengan baik bahwa bahkan untuk perhitungan sederhana tidak mungkin untuk memberikan apriori batas atas pada jumlah pita yang dibutuhkan mesin Turing untuk setiap perhitungan yang diberikan. Justru fitur ini yang membuat konsep Turing tidak realistis.

Dalam beberapa tahun terakhir gagasan tentang otomat terbatas telah muncul dalam literatur. Ini adalah mesin yang hanya memiliki sejumlah status internal terbatas yang dapat digunakan untuk memori dan komputasi. Pembatasan pada keterbatasan tampaknya memberikan perkiraan yang lebih baik terhadap gagasan mesin fisik. Tentu saja, mesin seperti itu tidak dapat melakukan sebanyak mesin Turing, tetapi keuntungan dari dapat menghitung fungsi rekursif umum sewenang-wenang dipertanyakan, karena sangat sedikit dari fungsi-fungsi ini muncul dalam aplikasi praktis.

Singkatnya, mereka dikembangkan sebagai model komputer nyata, yang memiliki sumber daya terbatas.

Alasan lain adalah model teoretis yang relatif praktis . Mesin Turing, terlepas dari ketidakmungkinan pita tak terbatas, adalah jenis yang canggung untuk apa rasanya memprogram komputer (perhatikan bahwa ini bukan analogi yang baik untuk memulai!). Namun PDA dan DFA cukup dapat diterima untuk menjadi model program aktual dalam arti bahwa desain PDA / DFA seringkali dapat dengan mudah diubah menjadi program nyata. Desain kompiler, misalnya, menggunakannya secara luas. Jadi pada titik-titik koneksi semacam ini antara teori dan praktik, kita mendapat pegangan tentang bagaimana semua itu saling berhubungan, dan apa yang bisa dan tidak bisa kita lakukan.

Lihat Game "Living Binary Adder" di sini: http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html Saya biasa menyajikan game ini kepada siswa saya di bab-bab awal tentang DFA / NFA. Ini menggambarkan dua hal penting dalam Teori Automata:

1. Bagaimana mengubah proses mental menjadi proses mekanis sederhana
2. Apa arti abstraksi sebenarnya. Dua status, seperti yang dinyatakan C dan Z di atas, dapat berupa apa saja: transistor di komputer, mekanisme hidrolik, atau dua pemain manusia!

Ini, terkadang membawa momen "Aha" kepada murid-murid saya.

Konsep DFA sangat berguna untuk merancang solusi yang efisien untuk berbagai jenis masalah. Salah satu contohnya adalah jaringan. Setiap protokol dapat diimplementasikan sebagai mesin negara. Menerapkan solusi dengan cara ini membuat kode lebih sederhana dan lebih sederhana berarti tingkat cacat yang lebih rendah. Ini juga berarti bahwa perubahan pada kode lebih mudah dan memiliki dampak yang lebih rendah, lagi-lagi memiliki tingkat cacat yang lebih rendah.

Beberapa orang merasa sulit untuk melihat protokol jaringan sebagai mesin negara tetapi mereka yang dapat melakukan lompatan merasa sangat bermanfaat dalam hal pengembalian usaha.

Sebenarnya, murid-murid saya kadang-kadang bertanya persis seperti ini - setelah menghabiskan sebagian besar semester pada automata terbatas dan akhirnya tiba di mesin Turing. Mengapa menghabiskan begitu banyak waktu pada formalisme yang lebih lemah ketika yang lebih kuat tersedia? Jadi saya menjelaskan tradeoff inheren dalam kekuatan ekspresif vs kompleksitas analitik. Model yang lebih kaya biasanya lebih sulit untuk dianalisis. Dikotomi DFA vs TM adalah ekstrem, karena masalah keanggotaan sepele untuk satu dan tidak dapat diperhitungkan untuk yang lain. Contoh yang kurang ekstrim adalah DFA vs PDA. Masalah keanggotaan untuk yang terakhir ternyata dapat dipecahkan secara efisien, tetapi solusinya sama sekali tidak sepele. Kami melihat kejadian ini di banyak cabang matematika dan sains: mempelajari model sederhana untuk mendapatkan pemahaman selengkap mungkin, yang biasanya mengarah pada wawasan ke model yang lebih kompleks juga.

Saya melihat beberapa jawaban menyebut FM "lebih rendah" daripada mesin Turing.

Fokus utama di kelas Pascasarjana saya ambil terletak pada kesetaraan mereka, bukan perbedaan. Untuk setiap model FSM yang kami pelajari, kami harus membuktikan kesetaraannya dengan Mesin Turing. Ini dilakukan dengan menerapkan Mesin Turing di FSM. IIRC, kami juga mempelajari beberapa model komputasi lain yang dingin tidak mengimplementasikan TM, tapi saya lupa apa itu. Intinya adalah, jika Anda dapat mengimplementasikan TM, Anda dapat menjalankan program TM apa pun pada model tersebut, diberi pita analog yang cukup besar untuk masalah yang sedang berjalan.

Dorongan dari jawaban untuk pertanyaan itu adalah: TM adalah model komputabilitas dasar, tetapi tidak terlalu praktis dalam hal membangun mesin yang bermanfaat. Oleh karena itu model FSM.

Ini dibawa pulang secara visual kepada saya ketika, pada sekitar waktu yang sama (1984), saya menemukan bahasa FORTH. Mesin eksekusi itu dibangun di atas realisasi murni dari Dual Stack PDA. Melangkah lebih dalam Saya menyukai mesin yang sama ini di bawah penyusun ekspresi

Meskipun, bagi saya, dampak nyata FSM adalah menemukan buku "Theory of Finite Automata" oleh Trakhtenbrot dan Korzynski (?) Ketika saya berusia 18 tahun, sebuah penemuan yang pada dasarnya memberi saya karier.