Hierarki Chomsky

Apa Itu Teori Bahasa & Otomata

Teori bahasa dan automata adalah bagian dari teori komputasi ilmu komputer. Bagian dari teori komputer berasal dari bahasa dan desain sistem, terutama yang berbasis matematika. Dalam hal ini, fokusnya adalah pada pemecahan masalah. Dengan menggunakan contoh-contoh yang menggambarkan masalah, latar belakang konsep dan hubungannya dengan definisi dan teorema yang ada dapat diidentifikasi. 

Teori bahasa dan automata diterapkan pada beberapa model digital, misalnya tentang pengembangan bahasa pemrograman dan kompiler. Meskipun tujuannya adalah untuk belajar teori Bahasa dan robot itu sendiri, yaitu. menambahkan dasar-dasar teori bahasa formal dan model mesin matematika yang menjelaskan cara kerja komputer.

Biasanya kita hanya mengenal bahasa seperti bahasa Inggris atau bahasa Indonesia. Bahasa adalah sekumpulan string abjad, sedangkan String itu sendiri adalah kata (kombinasi huruf) dalam bahasa, contoh rantai "Wayan Chandra". String juga bisa kosong dan ditandai dengan simbol ε. 

Apa Itu Teori Bahasa & Otomata Dalam Ilmu Komputer

Teori adalah sekumpulan konsep, prinsip, dan hipotesis yang digunakan untuk menjelaskan suatu fenomena atau peristiwa. Teori berfungsi sebagai kerangka acuan untuk memahami, menggambarkan, dan meramalkan gejala atau fenomena yang diobservasi dalam berbagai bidang ilmu, seperti sains, sosial, dan humaniora.

Teori memberikan konsep dan prinsip yang membantu untuk memahami perilaku masalah yang berhubungan dengan teori. Bidang ilmu komputer meliputi berbagai topik, mulai dari desain mesin hingga pemrograman. Selain perbedaan ada, ada keseragaman prinsip-prinsip umum yang digunakan. Untuk mempelajari prinsip-prinsip dasar ini, kami membuat mesin otomatis sebagai model abstrak komputer dan komputasi. Model ini memiliki fungsi penting dan umum dalam perangkat keras dan perangkat lunak komputer. Meskipun modelnya sederhana untuk diterapkan langsung ke dunia nyata, keuntungan yang didapat dari mempelajarinya adalah menyediakan landasan untuk dasar pengembangan algoritma. Pendekatan ini, juga diterapkan pada sains ilmu lainnya.

Klasifikasi Tata Bahasa 

Tata bahasa dapat secara formal didefinisikan sebagai seperangkat set variabel, simbol terminal, pembatas awal aturan produksi. Pada tahun 1959, pakar Noam Chomsky mengklasifikasikan tingkatan bahasa menjadi empat, disebut Hirarki Chomsky

Hierarki Chomsky adalah sistem klasifikasi tipe-tipe bahasa formal atau grammar yang dibagi menjadi empat tingkatan, yaitu tipe-0, tipe-1, tipe-2, dan tipe-3. Pada setiap tingkatan hierarki, terdapat aturan produksi dan variabel yang berbeda-beda. Berikut ini adalah penjelasan lebih detail tentang aturan produksi dan variabel pada masing-masing tingkatan hierarki Chomsky:

Tipe-0 (Bahasa Tak Terbatas)

Pada tingkat ini, aturan produksi dalam grammar tidak memiliki pembatasan apapun. Artinya, simbol non-terminal dapat diubah menjadi urutan simbol terminal atau simbol non-terminal yang sangat kompleks. Pada tingkat ini, variabel hanya terdiri dari simbol-simbol terminal dan non-terminal.

Contoh aturan produksi: S → abcD, AB → CDEFG, A → aBbC

Contoh variabel: S, D, AB, C, E, F, G, A, B

Tipe-1 (Bahasa Konteks-Sensitif)

Pada tingkat ini, aturan produksi dalam grammar memiliki batasan. Artinya, produksi gramatika harus berdasarkan konteks atau sejarah sebelumnya. Pada tingkat ini, simbol non-terminal hanya dapat diperluas menjadi urutan simbol terminal atau non-terminal yang lebih pendek dari simbol non-terminal asal. Pada tingkat ini, variabel terdiri dari simbol-simbol terminal dan non-terminal.

Contoh aturan produksi: AB → aBCD, aB → aaBb, S → λ

Contoh variabel: S, A, B, C, D

Tipe-2 (Bahasa Konteks-Bebas)

Pada tingkat ini, aturan produksi dalam grammar lebih sederhana daripada tipe-1. Simbol non-terminal hanya dapat diperluas menjadi urutan simbol terminal atau non-terminal yang lebih pendek daripada simbol non-terminal asal. Pada tingkat ini, variabel terdiri dari simbol-simbol terminal dan non-terminal.

Contoh aturan produksi: A → aB, S → ABc, B → ε

Contoh variabel: S, A, B, c, a

Tipe-3 (Bahasa Reguler)

Pada tingkat ini, aturan produksi dalam grammar sangat sederhana. Simbol non-terminal hanya dapat diperluas menjadi satu simbol terminal atau lambda (ε). Pada tingkat ini, variabel hanya terdiri dari simbol-simbol terminal.

Contoh aturan produksi: A → aB, S → aA, A → ε

Contoh variabel: S, A, B, a

Kesimpulannya adalah dimana aturan produksi dan variabel pada setiap tingkat hierarki memiliki kompleksitas yang berbeda-beda, dengan tingkat yang lebih tinggi memiliki aturan produksi dan variabel yang lebih kompleks daripada tingkat yang lebih rendah.