HIRARKI CHOMSKY

Sejarah Hirarki Chomsky

Pada tahun 1959,seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat,yang disebut dengan hirarki chomsky. Penggolongan tersebut bisa diketahui melalui tabel berikut....

Dalam hirarki Chomsky ada 4(empat) kelas pengelompokan suatu bahasa, yaitu:

 1. Reguler (Level/Tipe 3)

 Mesin Automata : Finate State Automata. DFA dan NFA

 Aturan:- Simbol sebelah kiri harus berupa simbol variabel.

             -  Simbol sebelah kanan maksimal hanya memiliki simbol variabel dan bila                ada terletak di paling kanan

 2. Bebas konteks (Level/Tipe 2)

 Mesin Automata : Push Down Automata

 Aturan: -  Simbol sebelah kiri harus simbol variabel

 3. Context Sensitive (Level/Tipe1)

 Mesin Automata: Linier Bounded Automata

 Aturan:-  Simbol pada ruas sebelah kiri harus minimal ada sebuah variabel

             -  |a| ≤ |b| artinya ruas sebelah kiri tidak lebih besar dari ruas sebelah                                        kanan.

 4. Unrectricted (Level/Tipe 0)

 Mesin Automata : Mesin Turing

 Aturan:- Simbol ruas sebelah kiri harus minimal ada sebuah simbol variabel

             -  Tidak ada batasan pada aturan produksi

• Secara umum tata bahasa dirumuskan sebagai berikut : α→β, yang berarti α menghasilkan β atau α menurunkan β. 

Di mana α menyatakan simbol-simbol pada ruas kiri aturan produksi (sebelah kiri tanda ‘→’) dan β menyatakan simbol-simbol pada ruas kanan aturan produksi (sebelah kanan tanda‘→’)

• Simbol variabel / non terminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar sepertiA, B, C, dst.
• Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a,b,c,dst.

Contoh Aturan Produksi

• T → a
  dibaca "T menghasilkan a"
• E →T | T + E  
  dibaca "E menghasilkan T" atau "E menghasilkan T dan E"

Simbol | menyatakan‘atau’, digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama.

1. Tipe 0 / Unrestricted / Natural Language 
   Aturan : 
1. Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel 
2. Tidak ada batasan pada aturan produksinya.
   Misal : 
• Abc → De (diterima) 
• ABC → b (diterima) 
• abc → GHI (ditolak, karena simbol pada sebelahkiri tidak ada sebuah simbol variabel)
  
  
2. Tipe 1 / Conteks Sensitive 
   Aturan : 
1. Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variable
2. Panjang string pada ruas kiri ≤ panjang string pada ruas kanan |α | ≤ |β|. 
   Misal : 
• Ab → DeF (diterima)
• CD → eF (diterima) exception : S → ε (diterima) 
• ABC → DE (ditolak, karena jumlah simbol pada ruas sebelah kiri lebih bayak dari jumlah simbol pada ruas kanan)
  
  
3. Tipe 2 / Bebas Konteks / Context Free 
   Aturan : 
1. Simbol pada Sebelah kiri harus berupa sebuah simbol variable 
   Misal : 
• B → CDeFG (diterima) 
• D → BcDe (diterima) 
• a → b (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)
4. Tipe 3/ Reguler 
   Aturan : 
1. Simbol pada Sebelah kiri harus berupa sebuah simbol variabel 
2. Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila ada terletak di posisi paling kanan. 
   Misal : 
• A  → e (diterima) 
• A  → fgh (diterima)
• A  → eH (diterima) 
• C → D (diterima) 
• A → Bc (Ditolak, karena simbol variabel pada sebelah kanan harus berada pada posisi paling kanan)

Catatan

• Aturan produksi seperti : 

1. ε →Abd 
   bukan aturan produksi yang legal, karena simbol ε tidak boleh berada pada ruas kiri 

• Aturan produksi yang ruas kirinya hanya memuat simbol terminal saja, seperti : 

1. a → bd 
2. ab → bd 
   bukan aturan produksi yang legal, karena ruas kiri juga harus memuat simbol yang bisa diturunkan.

Contoh Soal    

Grammar G1 dengan Q1= {S→aB,B→bB, B→b}.

Jawab:

  Ruas kiri semua produksinya terdiri dari sebuah VN maka G1 kemungkinan tipe CFG atau RG.Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string VT VN maka G1 adalah RG

F