Saya membaca " Rangkaian Bahasa Reguler dan Kompleksitas Deskripsional " oleh Galina Jiraskova, 2009 tentang kompleksitas negara yang dihasilkan dari penggabungan dua bahasa reguler (oleh Galina Jiraskova), tetapi saya tidak dapat memahami apa implikasi praktis kompleksitas negara nantinya . Pikiran sepele pertama yang mengejutkan saya adalah bahwa kompleksitas yang lebih tinggi akan membutuhkan lebih banyak waktu dan ruang oleh mesin. Apakah ini benar? Juga ada tempat lain di mana kompleksitas negara relevan dan penting?
Sunting: Kompleksitas status dari bahasa reguler adalah jumlah terkecil dari keadaan dalam setiap otomat terbatas deterministik (dfa) yang menerima bahasa. Kompleksitas keadaan tak-deterministik dari bahasa biasa didefinisikan sebagai jumlah terkecil dari keadaan dalam otomat terbatas nondeterministik (nfa) untuk bahasa itu.
Jawaban:
Kompleksitas negara benar-benar tentang deskripsi objek secara ringkas (dalam hal ini, bahasa biasa), bukan tentang kompleksitas komputasi. Topik umum disebut "kompleksitas deskriptif" dalam literatur dan menarik ilhamnya, sebagian, dari makalah klasik Meyer and Fischer tahun 1971 berjudul "Ekonomi Ekspresi oleh Automata, Tata Bahasa, dan Sistem Formal" (lihat http: // people .csail.mit.edu / meyer / economy-of-description.pdf ). Ini masih merupakan area aktif, dengan konferensi tahunan (DCFS - Descripional Complexity of Formal Systems).
Sedangkan untuk aplikasi, tempat di mana program Anda pada dasarnya bergantung pada mesin kondisi-terbatas (misalnya, parser) ada baiknya memiliki mesin kondisi-terbatas ini sekecil mungkin.
sumber
Izinkan saya menambahkan contoh konkret ke jawaban sempurna Jeffrey Shallit.
Misalkan Anda ingin membuat kamus Scrabble (TM). Anda dapat memikirkan beberapa cara untuk mewakili kamus Anda, seperti daftar kata, mencoba (pohon surat) atau automata deterministik. Menurut [1], meminimalkan trie menjadi dawg [= DFA] menghasilkan penghematan luar biasa dalam ruang; jumlah node berkurang dari 117.150 menjadi 19.853. Leksikon yang direpresentasikan sebagai daftar kata mentah membutuhkan waktu sekitar 780 Kbytes, sementara dawg kami dapat direpresentasikan dalam 175 Kbytes.
Seperti yang Anda lihat, kompleksitas negara sangat penting dalam kasus ini, terutama jika Anda ingin menulis program yang efisien seperti yang penulis lakukan.
[1] Appel dan Jacobson Program Scrabble Tercepat di Dunia , Komunikasi dari ACM 31 , 572-578 (1988).
sumber
Bukti bahwa dapat diputuskan apakah tata bahasa bebas konteks deterministik yang sewenang-wenang (atau setara dengan automat pushdown deterministik) memiliki otomat keadaan terbatas setara yang menggambarkan bahasa yang sama pada dasarnya adalah bukti kompleksitas keadaan otomat terbatas yang menggambarkan bahasa bebas konteks deterministik: terikat pada ukuran otomat terbatas ini dalam hal otomat deterministik memberikan batasan pada panjang prosedur keputusan.
Untuk detail, lihat " Keteraturan dan masalah terkait untuk automata pushdown deterministik. " Oleh Leslie G. Valiant.
sumber