Apa arti penting dari bahasa yang peka konteks (Tipe 1)?

Melihat bahwa dalam Chomsky Hierarchy Type 3 bahasa dapat dikenali oleh mesin negara tanpa memori eksternal (yaitu, otomat terbatas), Tipe 2 oleh mesin negara dengan tumpukan tunggal (yaitu otomat push-down) dan Tipe 0 oleh mesin negara dengan dua tumpukan (atau, ekuivalen, sebuah kaset, seperti halnya untuk Mesin Turing), bagaimana bahasa Tipe 1 cocok dengan gambar ini? Dan apa kelebihannya untuk menentukan bahwa suatu bahasa tidak hanya Tipe 0 tetapi Tipe 1?

Bahasa yang peka konteks adalah bahasa yang dapat dikenali oleh mesin Turing menggunakan ruang linear dan non-determinisme. Anda dapat mensimulasikan mesin Turing seperti menggunakan waktu eksponensial, sehingga Anda dapat mengenali bahasa tersebut dalam waktu eksponensial. Harap perhatikan bahwa masalah mengenali beberapa bahasa yang peka konteks adalah -complete, yang berarti kami cukup yakin Anda tidak bisa melakukan lebih baik daripada waktu eksponensial.$PSPACE$

Membandingkan ini dengan mengetikkan 0 bahasa, ini berarti Anda setidaknya bisa mengatakan sesuatu tentang berapa lama untuk mengenali bahasa tersebut. Bahasa tipe 0 bahkan mungkin tidak dapat diputuskan: bahasa dari semua mesin Turing yang berhenti adalah bahasa tipe 0, tetapi karena mengenali bahasa ini adalah masalah yang sebenarnya, itu tidak dapat diputuskan.

Tata bahasa konteks-sensitif tidak terlalu berguna dalam praktik. Context bebas tata bahasa yang intuitif untuk bekerja dengan, tetapi sebagai contoh di Wikipedia acara , context- sensitive tata bahasa sangat cepat menjadi agak berantakan. Program yang menggunakan ruang polinom jauh lebih mudah dirancang (dan menjamin adanya beberapa CSG yang setara yang hanya lebih besar secara polinomi dari penggunaan ruang algoritma Anda).$PSPACE$

Alasan keberadaan mereka adalah bahwa mereka membentuk ekstensi yang sangat alami dari tata bahasa bebas konteks (Anda mengizinkan konteks untuk menentukan produksi mana yang valid). Ini mungkin akan mengilhami Chomsky untuk mendefinisikan mereka dan menamai mereka bahasa tipe 1. Ingatlah bahwa definisi ini dibuat sebelum komputer menjadi secepat seperti sekarang ini: itu lebih menarik bagi ahli teori bahasa formal daripada untuk programmer.

Tata bahasa yang tidak dibatasi menjadi lebih aneh: tidak ada lagi gagasan 'memperluas' nonterminal dan menggantinya dengan produksi, mungkin tergantung pada konteksnya. Anda juga diperbolehkan untuk mengubah konteks secara bebas. Hal ini membuat tata bahasa yang tidak terbatas bahkan kurang intuitif untuk digunakan: program adalah setara dan jauh lebih intuitif.

Secara umum, Anda biasanya ingin mengetahui kelas yang lebih kecil di mana bahasa diberikan . Ini karena kelas yang lebih kecil dapat dikenali / diterima / dihasilkan oleh mekanisme yang lebih sederhana (automata, tata bahasa, ekspresi reguler, dll.), Yang diinginkan.$L$

Sebagai contoh, kelas bahasa reguler memiliki sifat penutupan yang baik , dan diberi DFA Anda dapat menguji dalam waktu linier bahwa sebuah kata milik . Sebaliknya, dengan mesin Turing Anda memerlukan waktu linier hanya untuk membaca output, yang biasanya terjadi sebelum benar-benar mulai diproses.$\mathcal{A}$$L(\mathcal{A})$

Singkatnya, untuk kelas yang lebih kecil Anda membutuhkan lebih sedikit daya komputasi untuk menyelesaikan masalah dalam memutuskan apakah suatu kata termasuk dalam bahasa.

Menurut Wikipedia , Chomsky mendefinisikan tata bahasa konteks-sensitif (yaitu Tipe 1) untuk menggambarkan sintaksis bahasa alami. Ini sedikit berbeda dibandingkan dengan kelas bahasa lainnya, yang diperkenalkan untuk menggambarkan keluarga string yang digunakan dalam matematika (misalnya sintaksis rumus aritmatika) alih-alih bahasa alami (misalnya sintaksis kalimat yang benar secara gramatik dalam bahasa Inggris) .

Dalam bahasa bebas konteks, pada titik mana pun dari penguraian input, otomat berada dalam keadaan yang ditentukan oleh tumpukannya. Setiap produksi memiliki perilaku yang sama dalam mengkonsumsi input terlepas dari di mana ia digunakan.

Ini mengarah ke properti yang menarik bahwa setiap produksi menghasilkan sub-bahasa dari yang dihasilkan oleh orang-orang yang lebih dalam tumpukan dan dengan demikian untuk setiap pasangan A dan B dari produksi yang dihasilkan dan dikonsumsi pada input tertentu kami memiliki tiga kemungkinan kasus:

• a: Input yang dikonsumsi oleh A sepenuhnya terkandung dalam input yang dikonsumsi oleh B; atau
• b: Input yang dikonsumsi oleh A sepenuhnya mengandung input yang dikonsumsi oleh B; atau
• c: Input yang dikonsumsi oleh A benar-benar terpisah dari input yang dikonsumsi oleh B.

Ini menyiratkan bahwa hal berikut tidak pernah terjadi:

• d: Input yang dikonsumsi oleh A sebagian tumpang tindih dengan input yang dikonsumsi oleh B.

Berbeda dengan itu, dalam bahasa konteks-sensitif, perilaku setiap produksi tergantung pada di mana ia digunakan, sehingga input yang dikonsumsi dalam produksi bukanlah sub-bahasa dari yang lebih dalam dalam tumpukan (pada kenyataannya, memprosesnya dengan tumpukan tidak akan bekerja). Dan kami memiliki kemungkinan bahwa d dapat terjadi.

Dalam dunia nyata, kasus di mana bahasa yang peka konteks akan masuk akal adalah sesuatu seperti menunjukkan <b> teks tebal </b>, <i> teks miring </i> dan <u> teks yang digarisbawahi </u> dengan tag html ini dan biarkan tumpang tindih, seperti "Ini adalah teks <u> dengan <i> campuran </u> tag yang tumpang tindih </i>." Amati bahwa untuk menguraikannya dan menemukan apakah semua tag awal cocok dengan tag akhir, PDA tidak akan melakukannya karena tidak bebas konteks, tetapi LBA akan dengan mudah melakukannya.

Properti Penutupan

Dari semua kelas bahasa dari hierarki Chomsky, hanya bahasa reguler dan peka konteks yang ditutup dengan komplemen . Karenanya ini adalah semacam fitur unik dari bahasa yang peka terhadap konteks.

Berbeda dengan bahasa bebas konteks, CS juga ditutup di bawah produk persimpangan dan acak .

Bahasa apa pun yang tipe 1 dapat dikenali oleh mesin Turing yang hanya menggunakan ruang linear (disebut linear bounded automata).

Bahasa tipe 1 dapat diputuskan dengan automata terikat linier , yang merupakan mesin Turing non-deterministik yang hanya dapat menggunakan sebagian dari pita yang ukurannya linier dengan ukuran input.

Hirarki Chomsky mengklasifikasikan tata bahasa lebih dari bahasa. Namun itu tidak dirancang untuk ada hubungannya dengan jumlah kaset automaton harus mengenalinya, seperti yang Anda sarankan untuk Tipe 2 dan 3, bahkan jika ada semacam mesin Turing yang melakukan itu untuk tata bahasa Tipe-1.

Anda juga harus mencatat bahwa bahasa tata bahasa Tipe-0 tidak semuanya dikenali oleh mesin Turing, tetapi mereka hanya dapat dihitung dengan mesin seperti itu: Tipe-0 berarti enumerable secara rekursif, dan mesin Turing hanya mengenali bahasa rekursif.

Bahasa pemrograman modern menggunakan fitur-fitur konteks-sensitif sepanjang waktu; mereka jatuh ke dalam subset yang secara efisien dapat diputuskan.

Contohnya adalah analisis nama dan tipe dan inferensi tipe.

Banyak orang lain telah menyebutkan bahwa bahasa Tipe-1 adalah bahasa yang dapat dikenali oleh automata terikat linier. Masalah penghentian adalah decidable untuk automata terikat linier, yang pada gilirannya berarti banyak properti lain yang secara komputasi tidak dapat ditentukan untuk bahasa yang dikenali oleh Turning Machines dapat dipilih untuk bahasa Tipe-1.

Diakui bukti bahwa masalah penghentian dapat diputuskan untuk automata terikat linier bergantung pada kenyataan bahwa dengan jumlah rekaman terbatas mereka hanya dapat memasukkan sejumlah negara terbatas, jadi jika mereka tidak berhenti dalam banyak langkah Anda tahu mereka perulangan dan tidak akan pernah berhenti. Bukti ini secara teknis berlaku untuk semua komputer yang sebenarnya (yang juga memiliki memori yang terbatas), tetapi itu tidak ada manfaat praktis dalam memecahkan masalah penghentian untuk program yang berjalan pada mereka.