Grammar dan Bahasa(Teori Bahasa&Otomata)

Sebelumnya membahas tentang Pengantar Teori Bahasa&Otomata, kali ini pembahasannya tentang Grammar dan Bahasa..

Simak dan pelajari yahh, semoga membantu

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 “ α à β “ (bisa 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 DAN KLASIFIKASI CHOMSKY

   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   (atau  himpunan token-token, atau alfabet) 

VN   : himpunan simbol-simbol non terminal 

S Є VN   : simbol awal (atau simbol start) 

Q  : himpunan produksi

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam 

Chomsky mengklasifikasikan 4 tipe grammar : 

Grammar tipe ke-0 : Unrestricted Grammar (UG) 

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

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

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

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

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

Grammar tipe ke-3 : Regular Grammar (RG) 

Ciri : α Є VN , β Є {VT , VTVN} atau α Є VN , β Є {VT, VNVT }

Contoh Analisa Penentuan Type Grammar

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

Grammar G2  dengan Q2  = {S → Ba,      B → Bb, B → b}. 

Jawab :

Ruas kiri semua produksinya terdiri dari sebuah VN maka G2  kemungkinan tipe CFG atau RG. 

Selanjutnya karena semua ruas  kanannya terdiri dari sebuah VT  atau string 

VNVT  maka G2  adalah RG

Grammar G3  dengan Q3  = {S → Ba,      B → bB, B → b}. 

Jawab :

Ruas kiri semua produksinya terdiri dari sebuah VN maka G3  kemungkinan tipe CFG atau RG. 

Selanjutnya karena ruas kanannya mengandung string VT VN  (yaitu bB) dan juga string VNVT  (Ba) maka G3  bukan RG, dengan kata lain G3  adalah CFG

Grammar G4 dengan Q4 = {S → aAb, B → aB}. 

Jawab :

Ruas kiri semua produksinya terdiri dari sebuah VN  maka G4  kemungkinan tipe CFG atau RG. 

Selanjutnya karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu aAb) maka G4  bukan RG, dengan kata lain G4  adalah CFG

Grammar G5  dengan Q5  = {S → aA,      S → aB, aAb → aBCb}. 

Jawab :

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 G5  adalah CSG

Tentukan bahasa dari masing-masing gramar berikut :

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)

     ¼

   Þ anAan  (2)

   Þ anban  (3)

Dari pola kedua kalimat disimpulkan : 

L1 (G1  ) = { anban ½ n ³ 1}

Tentukan bahasa dari masing-masing gramar berikut :

G2  dengan Q2  = {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)    Þ an-1S  (1)     

   Þ an B (2)

   Þ anbC   (3)

   Þ anbaC (4)

    ¼

    Þ anbam-1C (4)

    Þ an bam  (5)

Dari pola kedua kalimat disimpulkan : 

L2  (G2 ) = { an bam ½ n ³ 1, m ³ 1}

Grammar G6  dengan Q6 = {aS → ab,  SAc → bc}. 

Jawab :

Ruas kirinya mengandung string yang panjangnya lebih dari 1 maka G6  kemungkinan tipe CSG atau UG.

Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas kanannya (yaitu SAc) maka G6  adalah UG

Tentukan bahasa dari masing-masing gramar berikut :

G3 dengan Q3  = {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 (G3 ) = { anbn cn ½ n ³ 1}

Tentukan sebuah grammar regular untuk bahasa L1 = { an | n ≥ 1}

Jawab : 

Q1 (L1 ) = {S → aS | a}
S à a atau
S à aS à aa atau
S à aS à aaS à aaa

Tentukan sebuah grammar bebas konteks untuk bahasa :  

L2 : himpunan bilangan bulat non negatif ganjil

Jawab : 

Langkah kunci : digit terakhir bilangan harus ganjil.  

Buat dua buah himpunan bilangan terpisah : genap (G) dan ganjil (J) 

Q2(L2 ) = {S → J|GS|JS,  G → 0|2|4|6|8,           J → 1|3|5|7|9}

Tentukan sebuah gramar bebas konteks untuk bahasa : 

L3  = himpunan semua identifier yang sah menurut bahasa pemrograman Pascal 

dengan batasan : terdiri dari simbol huruf kecil dan angka, panjang identifier boleh lebih dari 8 karakter 

Jawab : 

Langkah kunci : karakter pertama identifier harus huruf.  

Buat dua buah himpunan bilangan terpisah : huruf (H) dan angka (A) 

Q3 (L3 ) = {S → H|HT, T → AT|HT|H|A,   H → a|b|c|…,  A → 0|1|2|…}

Contoh :

G1 :  VT = {I,  Love, Miss, You}, V = {S,A,B,C}, P = {S ® ABC, A® I, B® Love | Miss, C® You}

S Þ ABC

   Þ I loveYou 

L(G1)={I love You, I Miss You} 

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Reguler :

A à b
B à bdB
B à C
B à bC
B à Ad
B à bcdef
A à aSa
A à aSS
Ad à dB

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Bebas Konteks :

A à aSa
B à Ace
B à ab

B à bcdef
B à bcdefG
B à aSS
A à BCDEF
A à AAAA
Ad à dB

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Konteks Sensitive :

A à bcdefG
B à aSa
B à aSS
B à BCDEF
Ad à dB
ad à b
abC à DE
abcDef à ghijkl
AB à cde
AAA à BBB

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Unrestricted :

ad à b
abC à DE
AB à cde
ABCDEFG à h
bA à CDEFG

GRAMMAR DAN KLASIFIKASI CHOMSKY LANJT.

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  (atau  himpunan  token -token, atau alfabet)

VN : himpunan simbol-simbol non terminal

S Î VN  : simbol awal (atau simbol start)

Q : himpunan produksi

HIRARKI CHOMSKY

SEKIAN.