CHOMSKY HIERARCHY

Definisi Chomsky Hierarchy

Chomsky adalah salah satu pemrakarsa teori pemerolehan bahasa yang meyakini bahwa proses pemerolehan bahasa adalah suatu proses mental atau sebuah hirarki penahanan kelas tata bahasa formal. Yang digambarkan oleh Noam Chomsky pada tahun 1956. Hal ini juga dinami Marcel-Paul Schutzenberger, yang memainkan peran penting dalam pengembangan teori bahasa formal. Pada dasranya Chomsky Hierarchy ini memungkinkan kemungkinan bagi pemahaman dan penggunaan model ilmu komputer yang memungkinkan programmer untuk mencapai tujuan linguistik bermakna sistematis.

Noam Chosky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa. Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai saat ini belum diketahui bagaimana cara manusia mengartikan bahasa, sementara dengan pasti dapat mengartikan bahasa pada komputer. Noam Chomsky mengemukakan perangkat format yang disebut dengan grammar untuk memodelkan properti-properti bahasa. Grammar mempunyai nilai/manfaat sangat besar di ilmu informatika/komputer karena pencapaian ini digunakan untuk mendefinisikan dan mendeskripsikan sintaks bahasa pemrograman dan bahasa-bahsa formal lainnya. Grammar diterapkan pada perancangan kompilator dan bidang-bidang di ilmu komputer.

Bentuk Normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk Context Free Grammar (CFG). Bentuk Normal Chomsky dapat dibuat dari sebuah tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan . Dengan kata lain, suatu tata bahasa bebas konteks dapat diubah menjadibentuk normal Chomsky dengan syarat tata bahasa bebas konteks berikut:

·           Tidak memiliki produksi useless

·           Tidak memiliki produksi unit

·           Tidak memiliki produksi

Tipe-tipe Chomsky Hierarchy

            Noam Chomsky menyusun grammar dalam urutan yang dia sebut tipe 0, 1, 2 san 3. Tipe 0 adalah bentuk yang paling bebas dan paling sulit dikenali, biasa disebut recursively enumerable set, untuk mengenali bentuk ini biasa dipakai Turing Machine. Berikutnya adalah tipe 1 yang disebut context free grammar secara murni (tanpa tambahan metoda tertentu) adalah tidak cukup untuk pengolahan bahasa alami. Context Free Grammar sifat lebih mudah dipahami perilakunya dan pengolahannya serta masih dapat diolah dalam bentuk program yang terstruktur.

            Chomsky Hierarchy terdiri atas empat tipe yaitu:

1.        Tipe-0

Tipe-0 tata bahasa (grammar terbatas) mencangkup semua tata bahasa formal. Mereka menghasilkan persis semua bahasa yang bisa dikenali oleh mesin Turing. Bahasa ini juga biasanya disebut dengan bahasa rekursif enumerable.

2.        Tipe-1

Tipe-1 tata bahasa (grammar context-sensitive) menghasilkan bahasa konteks – sensitif. Tata bahasa ini memiliki aturan. Bahasa yang dijelaskan oleh tata bahasa ini sama persis dengan semua bahasa yang bisa dikenali oleh robot yang dibatasi oleh linear (mesin Turing nondeterministic yang dibatasi oleh waktu konstan panjang input).

3.        Tipe-2

Tipe-2 tata bahasa (bebas konteks) menghasilkan bahasa bebas konteks. Bahasa ini persis sama dengan semua bahasa yang dikenali oleh nondeterministic otomat pushdown. Bahasa bebas konteks merupakan dasar teoritis untuk sintaks bahasa pemrograman.

4.        Tipe-3

Tipe-3 tata bahasa (grammar biasa) menghasilkan bahasa biasa. Tata bahasa seperti ini membatasi aturan untuk nonterminal tunggal di sisi kiri dan sisi kanan yang terdiri dari satu terminal, mungkin diikuti (atau didahului, tetapi tidak dalam bahasa yang sama) oleh nonterminal tunggal. Bahasa ini persis sama dengan semua bahsa yang dapat diputuskan oleh negara yang terbatas. Selain itu, bahasa resmi dapat diperoleh dengan ekspresi reguler. Bahasa reguler biasanya digunakan untuk menentukan pola pencarian dan struktur leksikal bahasa pemrograman.

Tahap-Tahap Pembentukan Chomsky Hierarchy

Perbedaan Interpreter dan Compiler

·      Interpreter menterjemahkan baris per baris. Sedangkan compiler, menterjemahkan seluruh instruksi sekaligus. Selanjutnya hasil terjemahan (setelah melalui tahapan lain) bisa dijalankan secara langsung, tanpa tergantung lagi olelh program sumber atau compilernya.

·      Pada interpreter, penyusunan program relatif lebih cepat dan bisa langsung diuji sekalipun masih ada beberapa kesalahan secara kaidah dalam program. Sedangkan pada compiler, proses pembuatan dan pengujian membutuhkan waktu relatif lebih lama, sebab ada waktu untuk mengkompilasi (menerjemahkan) dan ada pula waktu untuk melakukan proses linking. Program akan berhasil dikompilasi hanya jika program tak mengandung kesalahan secara kaidah sama sekali.

·      Pada interpreter, kecepatannya menjadi lambat sebab sebelum suatu instruksi dijalankan selalu harus diterjemahkan telebih dahulu. Selain itu, saat program dieksekusi, interpreter juga harus selalu berada dalam memori. Jadi memori selalu digunakan baik untuk program maupun interpreter. Sedangkan pada compiler, proses eksekusi dapat berjalan dengan cepat, sebab tak ada lagi proses penerjemahan.

·      Pada interpreter, kode program tidak dapat dirahasiakan. Sdangkan pada compiler, kode program bisa dirahasiakan, sebab yang dieksekusi adalah program yang dalam bentuk kode mesin.