SURIANI D121181316_Chomsky hirarki

 Chomsky Hirarki Terhadap Bahasa/Grammar Komputasi

 

Tata bahasa (grammar) didefinisikan sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. 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.

a. Tata Bahasa Regular (Regular Grammar)/Tipe 3

α→β

dimana :

     α adalah sebuah simbol variabel

     β maksimal memiliki sebuah simbol variabel dan ditempatkan pada posisi paling kanan.

      Mesin pengenal bahasa disebut : Finite State Automata (FSA). 

 

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.

 

 

b. Tata Bahasa Bebas Konteks (Conteks Free Grammar)/Tipe 2

α→β

dimana :

       α adalah sebuah simbol variabel

       Mesin pengenal bahasa disebut : Push Down Automata (PDA). 

 

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

 

 

c. Tata Bahasa Sensitive Konteks (Conteks Sensitive Grammar)/Tipe 1 

α→β

dimana :

                IαI ≤ IβI

              Mesin pengenal bahasa disebut : Linear Bounded Automata (LBA).

  

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

 

 

d. Tata Bahasa Tanpa Batas (Unrestricted Grammar)/Tipe 0

Tidak ada batasan

Mesin pengenal bahasa disebut : Mesin Turing

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.