Apakah hierarki Chomsky sudah ketinggalan zaman?

45

Hirarki Chomsky (–Schützenberger) digunakan dalam buku teks ilmu komputer teoretis, tetapi itu jelas hanya mencakup sebagian kecil dari bahasa formal (REG, CFL, CSL, RE) dibandingkan dengan Diagram Kompleksitas Kebun Binatang . Apakah hierarki memainkan peran dalam penelitian saat ini lagi? Saya hanya menemukan sedikit referensi untuk Chomsky di sini di cstheory.stackexchange, dan di Complexity Zoo nama-nama Chomsky dan Schützenberger tidak disebutkan sama sekali.

Apakah penelitian saat ini lebih fokus pada cara deskripsi lain selain tata bahasa formal? Saya mencari metode praktis untuk menggambarkan bahasa formal dengan ekspresi yang berbeda, dan menemukan bahasa sensitif konteks yang berkembang (GCSL) dan bahasa pushdown (VPL), yang keduanya terletak di antara bahasa Chomsky klasik. Bukankah hierarki Chomsky diperbarui untuk memasukkan mereka? Atau apakah tidak ada gunanya memilih hierarki tertentu dari set lengkap kelas kompleksitas? Saya mencoba memilih hanya bahasa-bahasa yang sesuai dengan celah hierarki Chomsky, sejauh yang saya mengerti:

REG (= Chomsky 3) ⊊ VPL ⊊ DCFL ⊊ CFL (= Chomsky 2) ⊊ GCSL ⊊ CSL (= Chomsky 1) ⊊ R ⊊ RE

Saya masih belum mendapatkan di mana "bahasa yang agak peka konteks" dan "bahasa yang diindeks" cocok (di suatu tempat antara CFL dan CSL) meskipun tampaknya ada relevansi praktis untuk pemrosesan bahasa alami (tapi mungkin apa pun relevansi praktis kurang menarik dalam penelitian teoritis ;-). Selain itu Anda bisa menyebutkan GCSL ⊊ P ⊂ NP ⊂ PSPACE dan CSL ⊊ PSPACE ⊊ R untuk menunjukkan hubungannya dengan kelas P dan NP yang terkenal.

Saya temukan di GCSL dan VPL:

Saya juga akan senang jika Anda mengetahui buku teks terbaru tentang tata bahasa formal yang juga berhubungan dengan VPL, DCLF, GCSL dan tata bahasa yang diindeks, lebih disukai dengan pointer ke aplikasi praktis.

cc.complexity-theory automata-theory fl.formal-languages big-picture teaching Jakob
sumber
7
Poin minor: Saya tidak melihat tidak adanya nama Chomsky dan Schützenberger di Kebun Binatang Kompleksitas sebagai bukti bahwa "hierarki Chomsky sudah ketinggalan zaman." Hirarki Chomsky adalah gagasan dalam teori bahasa formal. Kompleksitas Zoo adalah situs web terutama tentang teori kompleksitas, meskipun memuat beberapa gagasan dalam teori bahasa formal seperti bahasa bebas konteks. Mereka terkait tetapi bidang yang berbeda. Akan ketinggalan jaman jika tidak disebutkan dalam buku teks dalam teori bahasa formal, tetapi saya tidak tahu apakah itu masalahnya.
Tsuyoshi Ito
7
Poin bagus, Tsuyoshi. Terus terang, saya ingin melihat "Kebun Binatang Bahasa Resmi" dengan landasan teori yang baik (referensi untuk makalah penelitian!) Tetapi juga sumber daya praktis. Misalnya ada puluhan varian sintaksis Backus-Naur-Form, dan varian Regular Expressions (beberapa di antaranya bahkan tidak reguler). Di samping hierarki Chomsky yang sederhana, saya merasa sulit mendapatkan gambaran yang jelas tentang keadaan penelitian terkini dalam bahasa formal.
Jakob
Anda juga dapat menambahkan bahasa bebas bintang di bawah bahasa biasa. Mereka seperti biasa, tetapi tanpa bintang Kleene. Terkenal. Berperilaku baik.
wren romano
Seperti yang ditunjukkan beberapa jawaban kepada saya, tata bahasa formal à la Chomsky adalah metode historis untuk menggambarkan bahasa formal, yang telah mencapai batasnya. Saya masih mencari ikhtisar tata bahasa formal yang bagus, yang tidak berfokus pada teori kompleksitas, tetapi terima kasih untuk semua referensi lebih lanjut! Saya akan menerima jawaban mgalle karena sejauh ini ia memiliki reputasi yang paling rendah.
Jakob
2
Dalam ilmu komputer, desain bahasa komputer, desain dan pemrograman perangkat lunak, tata bahasa dan bahasa bebas konteks dan ekspresi reguler dan bahasa adalah peralatan kerja dasar dan sama pentingnya dengan sebelumnya. Tetapi untuk tata bahasa yang semena-mena, LBA dan bahasa yang peka konteks, di sisi lain, saya telah melihat beberapa aplikasi atau tidak sama sekali.
reinierpost

Jawaban:

20

Dari apa yang saya lihat di komunitas Natural Language Processing, tata bahasa formal à la Chomsky tidak digunakan lagi. Mereka (juga) berpikir bahwa Hierarki Chomsky sudah ketinggalan zaman untuk memodelkan bahasa.

Apa yang terjadi adalah hal-hal seperti Re-writting rule (algoritma Lars), model ketergantungan (Dan Klein), Tata Bahasa Pengganti Pohon (model DOP), Tata Bahasa Fitur Biner (Alex Clark).

mgalle
sumber
Membaca ulang jawaban saya, itu terdengar lebih negatif daripada yang saya inginkan juga. RL dan CFL tidak pernah dianggap sebagai model realistik dari bahasa alami, dan sebagian besar model "baru" benar-benar terinspirasi di dalamnya.
mgalle
Saya berpikir bahwa RL bahkan tidak dirancang sebagai model bahasa alami, tetapi sebagai model perilaku sistem. [Teks asli Kleene juga tidak menggunakan terminologi bahasa formal.]
DG_
26

Singkatnya: ya.

Lebih khusus: Chomsky adalah salah satu yang pertama memformalkan hierarki yang berkaitan dengan bahasa, tata bahasa, dan automata. Wawasan ini masih sangat relevan dan diajarkan di semua kursus intro tentang teori automata. Namun, hierarki spesifik yang dihasilkan oleh Chomsky dan nama-nama untuk elemen-elemen hierarki tidak benar-benar signifikan lagi. Kami telah menemukan banyak formalisme yang berada di antara level hierarki Chomsky, di atasnya, atau di bawahnya. Dan nama-nama yang digunakan Chomsky tidak terlalu menarik, yaitu mereka tidak didasarkan pada ukuran kompleksitas yang menarik atau apa pun, mereka hanya angka. Haruskah bahasa yang agak peka konteks adalah Tipe-1.5 atau Tipe-1.7 atau Tipe-1.3? Siapa peduli. "Agak peka konteks" adalah nama yang jauh lebih informatif.

Kompleksitas Zoo agak sedikit berbeda karena penuh dengan segala macam persamaan kondisi dan sejenisnya. Hierarki yang lebih modern untuk teori automata tidak akan linear (misalnya, bandingkan CFG vs PEG) tetapi masih memiliki topologi yang terkenal. Untuk mendapatkan perspektif teori automata modern Anda harus melihat bekerja pada parser combinator libraries dan beberapa hal tentang unifikasi dan teori tipe (meskipun keduanya bercabang jauh).

wren romano
sumber
4
Kami menemukan nama yang lebih baik, ya. Itu tidak berarti bahwa hasilnya sudah ketinggalan zaman.
Raphael
4
@ Raphael: Yang ketinggalan zaman bukan karena namanya, karena itu karena hierarki spesifik yang diperkenalkan oleh Chomsky tidak digunakan lagi. Inklusi yang dijelaskan oleh hierarki Chomsky adalah (a) masih benar, dan (b) di antara inklusi dalam hierarki modern apa pun; tapi hirarki Chomsky seperti , adalah tidak kecuali sangat relevan bahwa hal itu terjadi untuk memukul beberapa poin yang tinggi terkenal. Orang tidak lagi melakukan penelitian tentang hierarki Chomsky, mereka melakukan penelitian di tempat lain. Ini tidak seperti menara polinomial yang memiliki alasan untuk nama / strukturnya.
wren romano
26

Jika ada sesuatu di TCS yang ketinggalan jaman, hierarki inklusi dari subset kecil kelas kompleksitas ini yang diketahui / dianggap menarik pada tahun 1956.

Beristirahatlah dengan tenang, Chomsky Hierarchy, dan semoga Anda menghantui kurikulum teori sarjana lagi.

Scott Aaronson
sumber
12
Seperti Juris Hartmanis pernah berteriak: "Bagaimana dengan kelas Chomsky ?? Kelas Chomsky adalah kekejian !!"
Ryan Williams
1
Ryan: Aku juga ingat Juris menyebut CH sebagai "kekejian"! Ketika saya menulis jawaban saya, saya berdebat apakah dia ingin komentarnya dipublikasikan. Tapi Anda mengenalnya lebih baik daripada saya ... :-D
Scott Aaronson
Komentar ini juga dapat dimotivasi setidaknya sedikit oleh pandangan merendahkan dari beberapa ilmu komputer teoretis dan matematikawan terhadap linguistik dan ilmu "lemah" lainnya: xkcd.com/435 . Tapi tentu saja hierarki Chomsky mengaburkan pandangan teori kompleksitas modern, jadi ini menjawab pertanyaan saya. Tetap akan menyenangkan untuk memiliki pengganti yang diperbarui untuk memulai dengan kurikulum teori sarjana, terutama jika Anda lebih tertarik pada bahasa formal dan tata bahasa untuk aplikasi praktis.
Jakob
1
Hirarki Chomsky mencantumkan kelas-kelas bahasa yang diurutkan berdasarkan kompleksitas deskripsi, bukan kompleksitas komputasi yang biasanya tersirat ketika Anda menggunakan istilah "teori kompleksitas". Mereka terkait, jelas. Lagi pula, saya masih gagal melihat bagaimana satu (kasar) hierarki dapat mengaburkan lebih banyak kelas halus yang sulit dipahami tanpa datang dari Chomsky Hierarchy. Mereka adalah pintu masuk!
Raphael
20

Jika Anda mempertimbangkan Hierarki Chomsky dengan nama "modern" (yaitu REG, LIN, CFL, CSL, RE resp. DFA / NFA, PDA, LBA, TM), saya katakan: Tidak, tidak ketinggalan jaman!

Alasan 0 : Masih benar dalam arti bahwa definisi dan hasilnya tidak bertentangan dengan pengetahuan yang lebih baru.

Alasan 1 : Model kelas / komputasi ini masih yang pertama kali Anda ajarkan - karena sederhana dan dipelajari dengan baik. Coba ajarkan otomat LR ke seorang mahasiswa sarjana tanpa meliput DFA / DPDA terlebih dahulu.

Alasan 2 : Kelas masih menjadi tolok ukur utama / utama untuk penemuan baru (saya membaca sekilas tentang multi-CFG yang, tentu saja, mengatakan: lebih dari CFG, kurang dari CSG). Itu mungkin sebagian karena mereka diajarkan pertama, tetapi juga karena mereka adalah sederhana dan dipelajari dengan baik.

Anti-Alasan 3 : Hasil tidak kedaluwarsa hanya karena kelas / model baru telah ditemukan. Mereka menjaga nilai mereka sebagai dasar-dasar lapangan meskipun mereka tidak digunakan di perbatasan penelitian aktif.

Raphael
sumber
10
"Matematika tidak menjadi tua , itu menjadi klasik ." (Sayangnya, saya tidak tahu kepada siapa kutipan ini dikaitkan.)
Heinrich Apfelmus
Bukankah maksud Anda "NPDA", bukan "DPDA"? Beberapa bahasa bebas konteks dikenali hanya oleh automata push-down nondeterministic.
Zsbán Ambrus
@ ZsbánAmbrus Benar sekali; Saya seharusnya menulis hanya "PDA". Terima kasih!
Raphael
Alasan terakhir tidak meyakinkan sama sekali (saya kira itu sebabnya itu alasan anti?). Banyak hasil yang ketinggalan jaman karena digolongkan atau kadang-kadang bahkan diremehkan oleh pendekatan yang berbeda untuk subjek. Saya tidak mengatakan ini kasusnya di sini, hanya saja alasan yang disebutkan tidak banyak bicara. Juga, nitpick gramatikal: "outdate" bukan kata kerja.
Sasho Nikolov
11

Saya pikir itu tergantung pada model perhitungannya. Jika Anda mempertimbangkan yang terbatas / pushdown / dll. automata sebagai model perhitungan, maka hierarki Chomsky menjadi penting (lihat misalnya buku Sipser). Di sisi lain, itu memainkan peran kecil dalam model komputasi Turing.

Ilustrasi berikut mungkin bermanfaat:

Sunting: Bahasa formal memainkan peran penting dalam mendesain bahasa komputer (seperti Java) dan kompiler, serta dalam pemrosesan bahasa alami (NLP).

MS Dousti
sumber
Maaf András, saya tidak dapat memahami komentar Anda. OP bertanya apakah hierarki Chomsky sudah usang. Alasannya adalah bahwa ia tidak melihatnya di kebun binatang kompleksitas, dll. Saya menjawab bahwa jika ia menganggap automata sebagai model komputasi, hierarki Chomsky menjadi relevan. Selain itu, saya menyebutkan bahwa kelas hierarki ini penting untuk desain kompiler dan algoritma NLP. IMHO, itu benar-benar terkait dengan pertanyaan itu.
MS Dousti
2
Tentu saja hierarki Chomsky tidak benar-benar ketinggalan zaman, ditemukan dalam sebagian besar pengantar ilmu komputer teoretis, bahasa formal, desain kompiler dll. Tapi selain itu, tampaknya tidak ada yang baru untuk diceritakan. Saya pikir terima kasih bahasa antara REG dan CFL, dan antara CFL, mungkin penting juga. Apakah ini ide yang buruk untuk memperluas hierarki dengan bahasa-bahasa ini karena hierarki Chomsky memiliki aroma "ketinggalan jaman" yang tidak penting untuk penelitian saat ini?
Jakob
Saya tidak berpikir itu ide yang buruk, meskipun kita harus menemukan beberapa aplikasi yang cocok dengan ekstensi baru.
MS Dousti