Tugas II. Contoh Klasifikasi Grammar Menurut Chomsky

Grammar dan Klasifikasi Chomsky

Grammar G didefinisikan sebagai pasangan 4 tuple : V _T , V _N , S, dan Q, dan dituliskan sebagai G(V _T , V _N , S, Q), dimana :

V_T : himpunan simbol-simbol terminal (atau himpunan token -token, atau alfabet)

V ^N : himpunan simbol-simbol non terminal

S ∈ V ^N : simbol awal (atau simbol start)

Q : himpunan produksi

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar yaitu :

1.      Grammar tipe ke-0 : Unrestricted Grammar (UG)

Ciri : α, β ∈ (V _T⎪ V_N )*, ⎪α⎪> 0

Tidak ada batasan pada aturan produksi

Contoh :

Abc → De

2.      Grammar tipe ke-1 : Context Sensitive Grammar (CSG)

Ciri : α, β ∈ (V _T ⎪V_N )*, 0 < ⎪α⎪ ≤ ⎪β⎪

Panjang string ruas kiri harus < (lebih kecil) atau = (sama dengan) ruas kanan

Contoh :

Ab → DeF

CD → eF

3.      Grammar tipe ke-2 : Context Free Grammar (CFG)

Ciri : α ∈ V N , β ∈ (V _T ⎪V _N )*

Ruas kiri haruslah tepat satu symbol variabel, yaitu simbol non terminal

Contoh :

B → CDeFg

D → BcDe

4.      Grammar tipe ke-3 : Regular Grammar (RG)

Ciri : α ∈ V N , β ∈ {V _T , V _T V _N } atau α ∈ V _N , β ∈ {V _T , V _N V_T }

Ciri-ciri RG sering dituliskan sebagai : α ∈ V _N , β ∈ {a, bC} atau α ∈ V _N , β ∈ {a,Bc}

Ruas kanan hanya memiliki maksimal satu symbol non terminal

Contoh :

A → e

A → efg

A → efgH

C → D

Tipe sebuah grammar (atau bahasa) ditentukan dengan aturan sebagai berikut :

A language is said to be type-i (i = 0, 1, 2, 3) language if it can be specified by a type-i grammar but can’t be specified any type-(i+1)grammar.

Gambar 1. Hirarki Chomsky

Contoh Analisa Penentuan Type Grammar

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

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.

2.      Grammar G₂ dengan Q₂ = {S → Ba, B → Bb, B → b}.

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_N V_T maka G₂ adalah RG.

3.      Grammar G₃ dengan Q₃ = {S → Ba, B → bB, B → b}.

Ruas kiri semua produksinya terdiri dari sebuah V_N maka G₃ kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung string V_T V_N (yaitu bB) dan juga string V_N V_T (Ba) maka G₃ bukan RG, dengan kata lain G₃ adalah CFG.

4.      Grammar G₄ dengan Q₄ = {S → aAb, B → aB}.

Ruas kiri semua produksinya terdiri dari sebuah V_N maka G₄ kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu aAb) maka G₄ bukan RG, dengan kata lain G₄ adalah CFG.

5.      Grammar G₅ dengan Q₅ = {S → aA, S → aB, aAb → aBCb}.

Ruas kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G₅ kemungkinan tipe CSG atau UG. Selanjutnya karena semua ruas kirinya lebih pendek atau sama dengan ruas kananya maka G₅ adalah CSG.

6.      Grammar G₆ dengan Q₆ = {aS → ab, SAc → bc}.

Ruas kirinya mengandung string yang panjangnya lebih dari 1 maka G₆ kemungkinan tipe CSG atau UG. Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas kananya (yaitu SAc) maka G₆ adalah UG.