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.
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.
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.