documentsn.com

10/09/2019Prio Handoko, S.Kom., M.T.I.Program Studi Informatika Universitas Pembangunan JayaBAB 4: Grammar dan bahasaPrio Handoko, S.Kom., M.T.I.Program Studi Informatika Universitas Pembangunan Jaya1

10/09/2019Bab 4: Grammar dan BahasaAgenda. Konsep Dasar Grammar dan Bahasa Grammar dan Klasifikasi Chomsky Derivasi Kalimat dan Penentuan BahasaGrammar dan Bahasa 3Konsep Dasar dan Bahasa Dalam pembicaraan grammar, anggota alfabet dinamakansimbol terminal atau token. Kalimat adalah deretan hingga simbol-simbol terminal. Bahasa adalah himpunan kalimat-kalimat dan anggotabahasa bisa tak hingga kalimat. Simbol-simbol berikut adalah simbol terminal: huruf kecil awal alfabet, misalnya: 𝑎, 𝑏, 𝑐simbol operator, misalnya: , , dan simbol tanda baca, misalnya: (, ), dan ;string yang tercetak tebal, misalnya: 𝒊𝒇, 𝒕𝒉𝒆𝒏, dan 𝒆𝒍𝒔𝒆.Grammar dan Bahasa 42

10/09/2019Konsep Dasar dan Bahasa Simbol-simbol berikut adalah simbol non terminal: huruf besar awal alfabet, misalnya: 𝐴, 𝐵, 𝐶; huruf S sebagai simbol awal; string yang tercetak miring, misalnya: expr dan stmt. Huruf besar akhir alfabet melambangkan simbol terminalatau non terminal, misalnya: 𝑋, 𝑌, 𝑍. Huruf kecil akhir alfabet melambangkan string yangtersusun atas simbol-simbol terminal, misalnya: 𝑥, 𝑦, 𝑧.Grammar dan Bahasa 5Konsep Dasar dan Bahasa Huruf yunani melambangkan string yang tersusun atassimbol-simbol terminal atau simbol-simbol non terminalatau campuran keduanya, misalnya: 𝛼, 𝛽, dan 𝛾. Sebuah produksi dilambangkan sebagai 𝛼 𝛽, artinya:dalam sebuah derivasi dapat dilakukan penggantian simbol𝛼 dengan simbol 𝛽. Simbol α dalam produksi berbentuk 𝛼 𝛽 disebut ruaskiri produksi sedangkan simbol 𝛽 disebut ruas kananproduksi.Grammar dan Bahasa 63

10/09/2019Konsep Dasar dan Bahasa Derivasi adalah proses pembentukan sebuah kalimat atausentensial. Sebuah derivasi dilambangkan sebagai: 𝛼 𝛽. Sentensial adalah string yang tersusun atas simbol-simbolterminal atau simbol-simbol non terminal atau campurankeduanya. Kalimat adalah string yang tersusun atas simbol-simbolterminal dan kalimat adalah kasus khusus dari sentensial. Pengertian terminal (terminate berakhir) dicapai, jikasentensial yang dihasilkan adalah sebuah kalimat yangtersusun atas simbol-simbol terminal itu.Grammar dan Bahasa 7Konsep Dasar dan Bahasa Pengertian non terminal (not terminate belum/tidakberakhir), jika sentensial yang dihasilkan masihmengandung simbol non terminal. Grammar G didefinisikan sebagai pasangan 4 tuple: VT, VN,S, dan Q, dan dituliskan sebagai G(VT , VN , S, Q), dimana:𝑽𝑻𝑽𝑵𝑺 𝑽𝑵𝑸: himpunan simbol-simbol terminal (atau himpunantoken – token, atau alfabet): himpunan simbol-simbol non terminal: simbol awal (atau simbol start): himpunan produksiGrammar dan Bahasa 84

10/09/2019Derivasi Kalimat dan Penentuan BahasaDerivasi adalah proses pembentukan sebuah kalimat atau sentensial.Sebuah derivasi dilambangkan sebagai: 𝛼 𝛽.Contoh.Tentukan derivasi kalimat dari grammar Q berikut.G dengan Q {1. S aAa, 2. A aAa, 3. A b}.Jawab.Derivasi kalimat terpendek:S aAa aba(1)(3)Grammar dan Bahasa 9Derivasi Kalimat dan Penentuan BahasaDerivasi kalimat umum:S aAa aaAaa . anAan anban(1)(2)(2)(3)Kesimpulan: L(G) {anban n 1}Grammar dan Bahasa 105

10/09/2019Derivasi Kalimat dan Penentuan BahasaLatihan 2.1. Tentukan derivasi kalimat terpendek dan kalimat umum darigrammar G1 dengan Q1 {1. S aS, 2. S aB, 3. B bC, 4. C aC, 5. C a}.2. Tentukan semua derivasi kalimat terpendek dari grammar G2 denganQ2 {1. S aSBC, 2. S abC, 3. bB bb, 4. bC bc, 5. CB BC, 6. cC cc}.Grammar dan Bahasa 11Grammar dan Klasifikasi ChomskyBerdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya(𝛼 𝛽), Noam Chomsky mengklasifikasikan 4 tipe grammar:1Grammar tipe ke-0: Unrestricted Grammar (UG) Ciri: 𝛼, 𝛽 𝑉𝑇 𝑉𝑁 ) , 𝛼 0Aturan: Tidak ada batasan pada aturan produksiContoh.Abc DeSAac AbcGrammar dan Bahasa 126

10/09/2019Grammar dan Klasifikasi Chomsky2Grammar tipe ke-1: Context Sensitive Grammar (CSG)Ciri: 𝛼, 𝛽 (𝑉𝑇 𝑉𝑁 ) , 0 𝛼 𝛽 Aturan: Panjang string ruas kiri harus (lebih kecil) atau (samadengan) ruas kananContoh.Ab DeFCD eFGrammar dan Bahasa 13Grammar dan Klasifikasi Chomsky3Grammar tipe ke-2: Contex Free Grammar (CFG)Ciri: 𝛼 𝑉𝑁 , 𝛽 (𝑉𝑇 𝑉𝑁 ) Aturan: Ruas kiri haruslah tepat satu simbol variabel, yaitu simbol nonterminalContoh.Ab DeFCD eFGrammar dan Bahasa 147

10/09/2019Grammar dan Klasifikasi Chomsky4Grammar tipe ke-3: Regular Grammar (RG)Ciri: 𝛼 𝑉𝑁 , 𝛽 {𝑉𝑇 , 𝑉𝑇𝑉𝑁 }, atau𝛼 𝑉𝑁 , 𝛽 {𝑉𝑇 , 𝑉𝑁𝑉𝑇 }Aturan: Ruas kanan hanya memiliki maksimal satu simbol nonterminalContoh.A eA efgA efgHC DGrammar dan Bahasa 15Grammar dan Klasifikasi ChomskyAnalisa Penentuan Type Grammar.Contoh.Tentukanlah type grammar G jika G memiliki Q {S aB, B bB, B b}.Jawab:Ruas kiri: Semua produksinya terdiri dari sebuah VN. maka Gkemungkinan tipe CFG atau RG.Ruas kanan: karena semua produksinya terdiri dari sebuah VT ataustring VTVN maka G adalah RG.Grammar dan Bahasa 168

10/09/2019Grammar dan Klasifikasi ChomskyLatihan 1.Tentukanlah type grammar G berikut:1.2.3.4.Q1 {S aAb, B aB}Q2 {aS ab, SAc bc}Q3 {S Ba, B Bb, B b}Q4 {S aA, S aB, aAb aBCb}Grammar dan Bahasa 17Operasi Dasar String Beberapa kesamaan: Kesamaan ke-1: (x*)* x* Kesamaan ke-2: ε x x ε x* Kesamaan ke-3: (x y)* ε x y xx yy xy yx .Until next Week Konsep Bahasa dan Otomata 189

Pengertian terminal (terminate berakhir) dicapai, jika sentensial yang dihasilkan adalah sebuah kalimat yang tersusun atas simbol-simbol terminal itu. Grammar dan Bahasa 7 Konsep Dasar dan Bahasa Pengertian non terminal (not terminate belum/tidak berakhir), jika sentens