HIRARKI CHOMSKY

HIRARKI CHOMSKY

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

 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 seperti A, B, C, dst.

—                  Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, dst.

 Selengkapnya...

CONTOHATURAN PRODUKSI ➢ T → a dibaca“T menghasilkan a“ ➢ E →T | T + E  dibaca“E menghasilkanT” atau “E menghasilkanT dan E“

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

Tipe 0 / Unrestricted / Natural Language

Aturan :

—                 Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel

—                 Tidak ada batasan pada aturan produksinya.

Misal :Abc	→ De	(diterima)
	ABC	→ b	(diterima)
pada sebelah kiri tidak	abc	→ GHI	(ditolak, karena simbol

ada sebuah simbol variabel)

Tipe 1/ Conteks Sensitive

Aturan :

—               Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variable

—               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)

Tipe 2 / Bebas Konteks/ Context Free

Aturan :

—                 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)

Tipe 3/ RegulerAturan :

Aturan :

—                 Simbol pada Sebelah kiri harus berupa sebuah simbol variabel

—                 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
posisi paling kanan)	berada pada

Contoh Soal :

—            Grammar G₁ dengan Q₁ = {S → aB, B → bB, B → b}.

—            Jawab :

Ruas kiri semua produksinya terdiri dari sebuah V_N maka G₁ kemungkinan tipe CFG atau RG.

Selanjutnya karena semua ruas kanannya terdiri dari sebuah V_T atau string

     V_T V_N  maka G₁  adalah RG