Dalam pengalaman saya, bahasa yang peka konteks dan automata terbatas linier sering dilewati atau dilompati dalam mata kuliah teori komputabilitas, dan bahkan ditinggalkan dari beberapa buku teks terkemuka, meskipun automata terbatas dan pushdown menerima banyak perhatian. Tentunya harus ada alasan bagus mengapa BBA diberikan lebih sedikit fokus daripada rekan-rekan mereka?
9
Jawaban:
Seharusnya sekarang cukup jelas mengapa kita tertarik pada dua yang pertama lebih dari LBA. Dua yang pertama secara alami cocok dengan definisi perhitungan layak yang biasa. Tetapi PSPACE tidak.
sumber
Nah, tanyakan kepada profesor Anda mengapa dia melakukannya. Saya hanya bisa menebak.
Mereka tidak semenarik Turing model lengkap dan PDA karena mereka berada dalam kekosongan * kesukaran yang mereka bagi, tentu saja, dengan padanan bahasa mereka: tidak sekuat mungkin, tetapi sudah sangat sulit dipecahkan.
Alasan lain mungkin karena tidak banyak yang diketahui (menebak di sini) tentang mereka, tetapi itu mungkin disebabkan oleh masalah ayam-telur.
(*) sengaja dibesar-besarkan
sumber
Tampaknya bukan hanya CSG tetapi juga CFG, ... sudah ketinggalan zaman akhir-akhir ini. Saya pikir hari ini automata dan PDA biasanya dianggap dalam mata kuliah teori komputabilitas / kompleksitas (jika ada) dan di sana mereka dimasukkan bukan untuk kepentingan mereka sendiri tetapi untuk memperkenalkan Mesin Turing.
Tata bahasa mungkin menarik untuk teori kompiler tetapi tidak terlalu banyak untuk komputabilitas / kompleksitas untuk dimasukkan dalam kursus sarjana pengantar. Ada terlalu banyak topik yang ingin dibahas tetapi kursus satu semester terlalu singkat dan kami harus memilih dan banyak dari topik ini yang tidak dapat kami bahas karena batasan waktu jauh lebih menarik daripada LBA.
sumber
Ekspresi reguler dan CFG digunakan dalam praktiknya untuk parsing kode (yaitu, bahasa pemrograman). Alasannya adalah bahwa ada algoritma yang sangat efisien untuk menguraikannya. Sebaliknya, BBA terlalu kuat untuk benar-benar digunakan dalam konteks itu.
Salah satu asal historis teori automata adalah subjek konstruksi penyusun. Karena alasan yang disebutkan di atas, hanya bahasa dan CFG biasa yang berguna untuk membangun kompiler (meskipun fakta bahwa tata bahasa atributif bukanlah CFG yang sebenarnya, dan bahwa algoritma parsing CFG tidak benar-benar menguraikan seluruh kelas CFG). LBA mungkin telah ditemukan oleh Chomsky sebagai tingkat kompleksitas menengah antara duniawi dan "Inggris". Jadi mungkin tempat yang tepat untuk mengajar mereka adalah dalam kursus linguistik daripada yang ilmu komputer!
sumber