Ada 4 (empat) kelas pengelompokan suatu bahasa, yang kita kenal dengan “Chomsky Hierarchy”. Hirarki atau tingkatan bahasa ini dikembangkan oleh Noam Chomsky pada tahun 1959.
Apa saja level yang berbeda dalam hierarki Chomsky?
Ada 4 level - Tipe-3, Tipe-2, Tipe-1, Tipe-0. Dengan setiap level, tata bahasa menjadi tidak terlalu ketat dalam aturan, tetapi lebih rumit untuk diotomatisasi. Setiap level juga merupakan bagian dari level berikutnya.
Tipe-3: Tata Bahasa Reguler - set paling ketat, mereka menghasilkan bahasa biasa. Mereka harus memiliki satu non-terminal di sisi kiri dan sisi kanan yang terdiri dari satu terminal atau terminal tunggal diikuti oleh satu non-terminal.
Tipe-2: Tata Bahasa Bebas Konteks - menghasilkan bahasa tanpa konteks, kategori yang sangat menarik bagi praktisi NLP . Di sini semua aturan mengambil bentuk A → β, di mana A adalah simbol non-terminal tunggal dan β adalah string simbol.
Type-1: Context-Sensitive Grammar - level tertinggi yang dapat diprogram, menghasilkan bahasa sensitif konteks. Mereka memiliki aturan bentuk α A β → α γ β dengan A sebagai non-terminal dan α, β, γ sebagai string terminal dan non-terminal. String α, β boleh kosong, tetapi γ harus tidak kosong.
Tipe-0: Tata bahasa yang dapat dihitung secara rekursif - terlalu umum dan tidak terbatas untuk mendeskripsikan sintaks dari bahasa pemrograman atau bahasa alami.
Apa istilah dan definisi umum yang digunakan saat mempelajari Hirarki Chomsky?
Simbol - Huruf, angka, karakter tunggal. Contoh - A, b, 3
String - Urutan simbol hingga. Contoh - Abcd, x12
Aturan Produksi - Kumpulan aturan untuk setiap tata bahasa yang menjelaskan cara membentuk string dari bahasa yang valid secara sintaksis.
Terminal - Unit tata bahasa terkecil yang muncul dalam aturan produksi, tidak dapat dirinci lebih lanjut.
Non-terminal - Simbol yang dapat diganti dengan non-terminal atau terminal lain dengan penerapan aturan produksi yang berurutan.
Grammar - Aturan untuk membentuk kalimat yang terstruktur dengan baik dan kata-kata yang membentuk kalimat tersebut dalam suatu bahasa. A 4-tupel G = (V, T, P, S) sedemikian rupa sehingga V = Himpunan tak-kosong terbatas dari simbol-simbol non-terminal, T = Himpunan hingga simbol terminal, P = Himpunan aturan produksi tak-kosong hingga, S = Simbol mulai
Bahasa - Kumpulan string yang sesuai dengan tata bahasa. Bahasa pemrograman memiliki string terbatas, sebagian besar bahasa alami tampaknya tidak terbatas. Contoh - Spanyol, Python, kode Heksadesimal.
Automaton - Versi tata bahasa yang dapat diprogram dan diatur oleh aturan produksi yang telah ditentukan sebelumnya. Ini telah menetapkan dengan jelas persyaratan komputasi memori dan pemrosesan. Contoh - Otomat biasa untuk ekspresi reguler.
Apa karakteristik bahasa yang sesuai di setiap level?
Di bawah tata bahasa Tipe-3 , kami tidak mengklasifikasikan seluruh bahasa karena aturan produksi dibatasi. Namun, konstruksi di dalam bahasa yang dapat dideskripsikan oleh ekspresi reguler termasuk dalam tipe ini.
Misalnya, aturan penamaan pengenal dalam bahasa pemrograman - ekspresi reguler dengan kombinasi huruf besar-kecil, beberapa karakter khusus dan angka, tetapi harus dimulai dengan huruf.
Bahasa bebas konteks yang diklasifikasikan sebagai Tipe-2 mampu menangani konstruksi bahasa penting yang disebut dependensi bersarang . Contoh bahasa Inggris - Kehadiran berulang dari "If <phrase> then <phrase>" - "Jika hari ini hujan dan jika saya tidak membawa payung, maka saya akan basah kuyup". Untuk bahasa pemrograman, tanda kurung fungsi atau loop yang cocok tercakup dalam tata bahasa ini.
Dalam bahasa Tipe-1 , menempatkan batasan pada produksi α → β dari struktur frase yang β setidaknya selama α, mereka menjadi peka konteks. Mereka mengizinkan penggantian α oleh β hanya dalam 'konteks', [konteks] α [konteks] → [konteks] β [konteks].
Terakhir, bahasa Tipe-0 tidak memiliki batasan pada tata bahasanya dan dapat berputar selamanya. Mereka tidak memiliki algoritme yang menghitung semua elemen.
Apa jenis Automaton yang mengenali tata bahasa di setiap level?
Type-3: Finite-State Automata - Untuk menghitung konstruksi untuk bahasa biasa, pertimbangan terpenting adalah tidak adanya kebutuhan memori. Pikirkan mesin penjual otomatis untuk tiket platform atau algoritme lift. Otomaton mengetahui keadaan saat ini dan keadaan selanjutnya yang diizinkan, tetapi tidak 'mengingat' langkah-langkah sebelumnya.
Type-2: Push-Down Automata - Untuk mencocokkan dependensi bersarang, robot ini membutuhkan tumpukan memori satu ujung. Misalnya, untuk mencocokkan jumlah frasa 'jika' dan 'lain', robot perlu 'mengingat' yang terakhir terjadi 'jika'. Hanya dengan begitu ia dapat menemukan 'lain' yang sesuai.
Type-1: Linear-Bounded Automata - adalah bentuk mesin Turing terbatas yang bukannya tidak terbatas, melainkan dibatasi oleh beberapa fungsi linier yang dapat dihitung. Keuntungan dari robot ini adalah bahwa kebutuhan memorinya (batas atas RAM) dapat diprediksi bahkan jika eksekusinya bersifat rekursif di beberapa bagian.
Tipe-0: Mesin Turing - Fungsi yang tidak dapat dihitung ada dalam Matematika dan Ilmu Komputer. Namun, mesin Turing memungkinkan merepresentasikan fungsi seperti itu sebagai urutan langkah-langkah terpisah. Kontrol itu terbatas meskipun data mungkin tampak tidak terbatas.
Contoh singkat untuk setiap jenis tata languange / grammar?
Type-3: Regex untuk mendefinisikan token seperti pengenal, kata kunci bahasa dalam bahasa pemrograman. Mesin penjual koin yang hanya menerima koin 1-Rupee, 2-Rupee dan 5-Rupee memiliki bahasa biasa dengan hanya tiga kata - 1, 2, 5.
Tipe-2: Blok pernyataan dalam bahasa pemrograman seperti fungsi dalam tanda kurung, If-Else, untuk loop. Dalam bahasa alami, kata benda dan bentuk jamaknya dapat dikenali melalui satu NFA , kata kerja dan bentuknya yang berbeda dapat dikenali melalui NFA lain , lalu digabungkan. Singular (Gadis berlari pulang -> Gadis + Berlari). Jamak (Gadis-gadis lari pulang -> Girls + Run)
Jenis-1: Meskipun sebagian besar konstruksi bahasa dalam bahasa natural bebas konteks, dalam beberapa situasi pencocokan linear token harus dilakukan, seperti - "Akar kuadrat dari 16, 9, dan 4 adalah 4, 3, dan 2. " Di sini 16 harus dicocokkan dengan 4, 9 dicocokkan dengan 3, dan 4 dicocokkan dengan 2.
Tipe-0: Bahasa tanpa batasan tidak kondusif untuk komunikasi atau otomatisasi. Karenanya tidak ada contoh umum untuk jenis ini. Namun, beberapa persamaan matematis yang tampaknya tidak terpecahkan dinyatakan dalam bentuk ini.
Referensi :
Comments