Uncategorized

GRAMMAR & 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 :
VT : himpunan simbol-simbol terminal (atau himpunan token -token, atau
alfabet)
VN : 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 :

  1. Grammar tipe ke-0 : Unrestricted Grammar (UG)
    Ciri : α, β ∈ (V T VN )*, α> 0
  2. Grammar tipe ke-1 : Context Sensitive Grammar (CSG)
    Ciri : α, β ∈ (V T VN )*, 0 < α ≤ β
  3. Grammar tipe ke-2 : Context Free Grammar (CFG)
    Ciri : α ∈ V N , β ∈ (V T VN )*
  4. Grammar tipe ke-3 : Regular Grammar (RG)
    Ciri : α ∈ V N , β ∈ {V T , V T VN } atau α ∈ V N , β ∈ {V T , V N VT }
    Mengingat ketentuan simbol-simbol (hal. 3 no. 4 dan 5), ciri-ciri RG sering
    dituliskan sebagai : α ∈ V N , β ∈ {a, bC} atau α ∈ V N , β ∈ {a, Bc}
    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.
    Contoh Analisa Penentuan Type Grammar
  5. Grammar G1 dengan Q1 = {S → aB, B → bB, B → b}. Ruas kiri semua
    produksinya terdiri dari sebuah V N maka G1 kemungkinan tipe CFG atau RG.
    Selanjutnya karena semua ruas kanannya terdiri dari sebuah V T atau string
    VT VN maka G1 adalah RG.
  6. Grammar G 2 dengan Q 2 = {S → Ba, B → Bb, B → b}. Ruas kiri semua
    produksinya terdiri dari sebuah V N maka G 2 kemungkinan tipe CFG atau RG.
    Selanjutnya karena semua ruas kanannya terdiri dari sebuah V T atau string
    VN VT maka G 2 adalah RG.
  7. Grammar G3 dengan Q 3 = {S → Ba, B → bB, B → b}. Ruas kiri semua
    produksinya terdiri dari sebuah V N maka G 3 kemungkinan tipe CFG atau RG.
    Selanjutnya karena ruas kanannya mengandung string V T V N (yaitu bB) dan juga
    string V N VT (Ba) maka G 3 bukan RG, dengan kata lain G 3 adalah CFG.
  8. Grammar G 4 dengan Q 4 = {S → aAb, B → aB}. Ruas kiri semua produksinya
    terdiri dari sebuah V N maka G 4 kemungkinan tipe CFG atau RG. Selanjutnya
    karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu
    aAb) maka G 4 bukan RG, dengan kata lain G 4 adalah CFG.
  9. Grammar G5 dengan Q 5 = {S → aA, S → aB, aAb → aBCb}. Ruas kirinya
    mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G5
    kemungkinan tipe CSG atau UG. Selanjutnya karena semua ruas kirinya lebih
    pendek atau sama dengan ruas kananya maka G 5 adalah CSG.
  10. Grammar G 6 dengan Q 6 = {aS → ab, SAc → bc}. Ruas kirinya mengandung
    string yang panjangnya lebih dari 1 maka G 6 kemungkinan tipe CSG atau UG.
    Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas
    kananya (yaitu SAc) maka G 6 adalah UG.

Derivasi Kalimat dan Penentuan Bahasa
Tentukan bahasa dari masing-masing gramar berikut :

  1. G1 dengan Q1 = {1. S → aAa, 2. A → aAa, 3. A → b}.
    Jawab :
    Derivasi kalimat terpendek : Derivasi kalimat umum :
    S ⇒ aAa (1) S ⇒ aAa (1)
    ⇒ aba (3) ⇒ aaAaa (2)

    ⇒ a n Aa n (2)
    ⇒ a n ba n (3)
    Dari pola kedua kalimat disimpulkan : L1(G1 ) = { a n ba n  n ≥ 1}
  2. G2 dengan Q 2 = {1. S → aS, 2. S → aB, 3. B → bC, 4. C → aC, 5. C → a}.
    Jawab :
    Derivasi kalimat terpendek : Derivasi kalimat umum :
    S ⇒ aB (2) S ⇒ aS (1)
    ⇒ abC (3) …
    ⇒ aba (5) ⇒ a n-1S (1)
    ⇒ a nB (2)
    ⇒ a nbC (3)
    ⇒ a n baC (4)

    ⇒ a n ba m-1C (4)
    ⇒ a n ba m (5)
    Dari pola kedua kalimat disimpulkan : L 2 (G 2 ) = { a n ba m  n ≥ 1, m ≥ 1}
  3. G3 dengan Q 3 = {1. S → aSBC, 2. S → abC, 3. bB → bb,
  4. bC → bc, 5. CB → BC, 6. cC → cc}.
    Jawab :
    Derivasi kalimat terpendek 1: Derivasi kalimat terpendek 3 :
    S ⇒ abC (2) S ⇒ aSBC (1)
    ⇒ abc (4) ⇒ aaSBCBC (1)
    Derivasi kalimat terpendek 2 : ⇒ aaabCBCBC (2)
    S ⇒ aSBC (1) ⇒ aaabBCCBC (5)
    ⇒ aabCBC (2) ⇒ aaabBCBCC (5)
    ⇒ aabBCC (5) ⇒ aaabBBCCC (5)
    ⇒ aabbCC (3) ⇒ aaabbBCCC (3)
    ⇒ aabbcC (4) ⇒ aaabbbCCC (3)
    ⇒ aabbcc (6) ⇒ aaabbbcCC (4)
    ⇒ aaabbbccC (6)
    ⇒ aaabbbccc (6)
    Dari pola ketiga kalimat disimpulkan : L 3 (G 3 ) = { a n b n c n  n ≥ 1}

Web Refrensi : https://www.budiluhur.ac.id/

Leave a Reply

Your email address will not be published. Required fields are marked *