Grammar

 Grammar

Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel,Simbol-simbol terminal,simbol awal,yang dibatasi oleh aturan - aturan produksi. Aturan produksi merupakan pusat dari grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya. 

  Semua aturan produksi dinyatakan dalam bentuk "Ⲁ→β" (Dibaca Ⲁ menghasilkan β,atau dibaca  Ⲁ menurunkan  β).  Ⲁ merupakan simbol - simbol pada ruas kiri aturan produksi,sedangkan β merupakan simbol - simbol ruas kanan aturan produksi. 

  Simbol - simbol tersebut dapat berupa simbol terminal (Vt) atau simbol NON Terminal (Vn)/Variabel.Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar (‘A’,’B’,’C’). Simbol Vt adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil (‘a’,’b’,’c’). 

Dengan menerapkan aturan produksi suatu grammar bisa menghasilkan sejumlah String Contoh aturan produksi ; E→T | T+E | T * E 

                                        T→a

 Dari aturan produksi di atas, menghasilkan suatu variabel a atau variabel ekspresi a+a atau
a*a
E→T
T→a
E→T+E
E→a+T
E→a+a
E→T*E
E→a*T
E → a*a

Grammar G didefinisikan sebagai pasangan 4 tuple :

VT , VN , S, dan Q, dan dituliskan sebagai G(VT, VN, S,Q), dimana :

VT        : himpunan simbol-simbol terminal (atauhimpunan token-token, atau alfabet)

VN       : himpunan simbol-simbol non terminal

SЄVN  : simbol awal (atau simbol start)

Q         : himpunan produksi

Contoh :

          1.  G₁ :  V_T = {I,  Love, Miss, You}, V = {S,A,B,C},

               P = {S →ABC, A→ I, B→ Love | Miss, C→ You}

    S → ABC

    S →IloveYou

  L(G1)={IloveYou, IMissYou}

PENGKLASIFIKASIAN GRAMMAR

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

1. Grammar tipe-0 : UNRESTRICTED GRAMMAR (UG)

          Ciri : α, β ϵ (VT | VN)*, | α | > 0

2. Grammar tipe-1 : CONTEXT SENSITIVE GRAMMAR (CSG)

         Ciri : α, β ϵ (VT | VN)*, 0 < | α | ≤ | β |

3. Grammar tipe-2 : CONTEXT FREE GRAMMAR (CFG)

         Ciri : α ϵ VN , β ϵ (VT | VN)*

4. Grammar tipe-3 : REGULLAR GRAMMAR (RG)

        Ciri : α ϵ VN , β ϵ {VT , VT VN} atau α ϵ VN , β ϵ {VT , VN VT }
        Mengingat ketentuan simbol-simbol  maka ciri RG sering ditulis sebagai :
        α ϵ VN , β ϵ {a , bC}  atau α ϵ VN , β ϵ {a , Bc}

 Contoh analisa penentuan type grammar
1. Grammar G1 dengan Q1 = {S→aB, B→bB, B→b}.
2. Grammar G2 dengan Q2 = {S→Ba, B→bB, B→b}.
Jawab :

1. Grammar G1 dengan Q1 = {S→aB, B→bB, B→b}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G1 kemungkinan type CFG atau RG
   Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau String VT VN maka G1 adalah RG

2. Grammar G2 dengan Q2 = {S→Ba, B→bB, B→b}.  Ruas kiri semua produksinya terdiri dari sebuah VN maka G2 kemungkinan type CFG atau RG.