Klasifikasi Grammar menurut Chomsky

 

Klasifikasi Grammar menurut Chomsky

1.      TATA BAHASA (GRAMMAR)

Bahasa merupakan himpunan kalimat (baik terhingga maupun tak terhingga). Bahasa dapat disajikan dengan menyebut kalimatnya satu persatu. Untuk bahasa tak hingga, penyebutan seperti itu tidak mungkin. Oleh karena itu diciptakan cara penyajian yang mendeskripsikan bahasa secara efisien. Cara penyajian tersebut adalah Tata Bahasa atau Grammar.

Sebuah Tata Bahasa (Grammar) didefinisikan sebagai 4 tupel :

            G = (V_n, V_t, S, Q)

V_n dan V_t adalah simbol Non Terminal dan Simbol Terminal.

S adalah sebuah elemen anggota V_n yang disebut Simbol Start.

Q merupakan himpunan Produksi.

Chomsky mengelompokkan Grammar menjadi 4 kelompok :

1.      Tipe nol : UnRestricted Grammar (Tata Bahasa Tidak Terbatasi)

Tata Bahasa UnRestricted yang tidak merupakan anggota dari klasifikasi lainnya ditandai dengan aturan produksi yang bagian sebelah kirinya lebih panjang dari bagian sebelah kanan. Aturan produksi yang mengandung simbol hampa (^) pasti merupakan Tata Bahasa UnRestricted dan tidak termasuk klasifikasi lainnya.

2        Tipe satu : Context Sensitive Grammar (Tata Bahasa Tergantung Konteks)

Tata bahasa ini terdiri dari produksi berbentuk :

a ® b  dengan  ½a½  <==  ½b½

dimana a adalah string dan ½a½ adalah panjang string a demikian juga b adalah string dan ½b½ adalah panjang string b. String adalah merupakan deretan simbol baik terminal maupun non terminal.

Contoh :

G = ( {S, B, C}, {a, b, c}, S, Q )

Dimana Q terdiri dari produksi berikut :

1.      S     ® aSBC ½ abC

2.      bB  ® bb

3.      BC ® bc

4.      CB ® BC

5.      CC ® cc

1.      Tipe dua : Context Free Grammar ( Tata Bahasa Bebas konteks)

Tata bahasa ini terdiri dari produksi berbentuk :

a ® b  dengan  ½a½  <==  ½b½

dimana a adalah anggota V_n sedangkan b adalah string. Berarti Context Free Grammar seluruh produksi ruas kirinya hanya terdiri dari satu simbol yaitu simbol non terminal.

Contoh :

G = ( {S, C}, {a, b}, S, Q )

Dimana Q terdiri dari produksi berikut :

1.      S ® aSa

2.      S ® aCa

3.      C ® b

2.      Tipe tiga : Regular Grammar

Tata bahasa ini terdiri dari produksi berbentuk :

a ® b  dengan  ½a½  <==  ½b½

dimana a adalah anggota V_n dan b mempunyai bentuk aB atau a dengan a anggota V_t dan B anggota V_n.

Contoh :

G = ( {S, A, B, C}, {a, b}, S, Q )

Dimana Q terdiri dari produksi berikut :

1.      S ® aS ½ aB

2.      B ® bC

3.      C ® aC

4.      C ® a

Regular Grammar merupakan subset dari Context Free Grammar.

Context Free Grammar merupakan subset dari Context Sensitive Grammar.

Context Sensitive Grammar merupakan subset dari UnRestricted Grammar.