HIRARKY CHOMSKY

Pengelompokan Bahasa

   

Tata Bahasa (grammer) bisa didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Pada tahun 1959 seorang ahli bernama Noam Chomsky melakukan pengelompokkan tingkatan bahasa menjadi empat, yang disebut dengan Hirarki chomsky. Pengelompokkan tersebut dapat dilihat pada tabel berikut :

Bahasa	Mesin Automata	Aturan Produksi
Regular (Tipe 3)	FSA meliputi DFA, NFA	a adalah sebuah simbol variabel. b maksimal memiliki sebuah simbol variabel yang bila ada terletak diposisi paling kanan.
Bebas Konteks (Tipe 2)	Push Down Automata	a berupa sebuah simbol variable
Context Sensitive (Tipe 1)	Linear Bounded Automata	| a | £ | b |
Natural Language (Tipe 0)	Mesin Turing	Tidak ada batasan

Disini semua aturan produksi dalam bentuk a  à b ( ‘dibaca a menghasilkan b’ ), dimana : a menyatakan simbol-simbol pada ruas kiri aturan produksi dan  b menyatakan simbol-simbol pada ruas kanan aturan produksi (atau hasil produksi). Simbol-simbol tersebut dapat berupa simbol terminal (non variabel) atau simbol variabel. Simbol terminal adalah simbol-simbol yang tidak  dapat diturunkan kembali, sedangkan simbol variabel adalah simbol yang masih bisa diturunkan kembali. Dalam penulisannya, simbol-simbol variabel digunakan huruf kapital (‘A’, ‘B’ dll), sedangkan simbol-simbol terminal digunakan  huruf kecil (‘a’, ‘b’, dll). 

Level-level Bahasa

    

Dalam hirarki chomsky, terdapat empat level bahasa yaitu level 0 (Natural Language),  level 1 (Contex sensitive), level 2 (Bebas Konteks), dan level 3 (Regular). Dari setiap level tersebut terdapat aturan-aturan  produksi yang membatasinya. Contoh-contoh aturan produksi untuk setiap level bahasa :

1.            Level 0 (Natural Language)

Bahasa manusia termasuk kedalam tipe ini, dimana tidak ada batasan untuk aturan produksinya.

Contoh :

a.       Abc à aa

b.      Bc à aBaB

c.       CaB à aaBaaBa

2.            Level 1 (Contex sensitive)

Panjang string di ruas kiri (a) £   panjang string ruas kanan (b ).

Contoh :

a.       Ab à aBa

b.      cD à aB

c.       dEd à FabCa

3.            Level 2 (Bebas Konteks)

α adalah sebuah simbol variabel, dan batasannya bertambah bahwa ruas kiri harus tetap satu simbol variabel.

Contoh :

a.       A à aa

b.      B à aBD

c.       C à FGaa

4.            Level 3 (Regular)

Batasannya bertambah lagi, dimana ruas kanan maksimal memiliki sebuah simbol variabel yang terletak paling kanan. Artinya bisa memiliki simbol terminal dengan jumlah tidak dibatasi, tetapi bila terdapat simbol variabel maka simbol variabel tersebut hanya berjumlah satu (1) dan terletak paling kanan.

Contoh :

a.       A à aa

b.      B à aaB

c.       C à aaaaa