08 cfg
Download as ppsx, pdf0 likes688 views
Dokumen ini membahas tata bahasa bebas konteks (CFG) dan penggunaannya dalam menjelaskan struktur bahasa alami manusia dan bahasa pemrograman. Dalam CFG, terdapat komponen nonterminal dan terminal, serta aturan produksi yang mendefinisikan cara penurunan kalimat. Selain itu, dokumen menjelaskan konsep keambiguan dalam penurunan dan mencakup contoh-contoh serta latihan yang berkaitan dengan CFG.
08 cfg
- 1. Tata Bahasa Bebas Konteks (Context-Free Grammar) Pertemuan ke-8 dan ke-9 Yenni Astuti, S.T., M.Eng. yenni.stta@gmail.com
- 2. Tujuan Penggunaan Context-Free Grammar (CFG) Menjelaskan bahasa alami manusia Contoh 1: Aturan Kalimat pada Bahasa Manusia <sentence> <noun phrase> <verb phrase> <noun phrase> <adjective> <noun phrase> <noun phrase> <noun> **Tanda dibaca: diturunkan menjadi
- 3. Contoh 1 (lanjutan): Aturan Kalimat pada Bahasa Manusia <sentence> <noun phrase> <noun phrase> <verb phrase> <verb phrase> <verb> <noun> <adjective> <noun phrase> <verb phrase> <adjective> <noun phrase> <noun> <verb> <noun phrase> <verb> love boy, girl little, pretty **Tanda dibaca: diturunkan menjadi
- 4. Nonterminal danTerminal pada Bahasa Alami Manusia <verb> <noun> <adjective> love boy, girl little, pretty Simbol di dalam tanda < > adalah simbol nonterminal. love, boy, pretty adalah simbol terminal.
- 5. Contoh 2: Penurunan kalimat Little boy love pretty girl dari Aturan slide 3 <sentence> <noun phrase> <verb phrase> <adjective> <noun phrase> <verb phrase> little <noun> <verb phrase> little boy <verb phrase> little boy <verb> <noun phrase> little boy love <noun phrase> little boy love <adjective> <noun phrase> little boy love pretty <noun phrase> little boy love pretty <noun> little boy love pretty girl
- 6. Manfaat CFG pada bidang Komputer Mendeskripsikan aturan tata bahasa suatu bahasa pemrograman (seperti: C, Pascal, Basic)
- 7. Definisi Formal CFG CFG dituliskan dalam bentuk 4 komponen (4-tupel) G = (N, , P, S) N = himpunan nonterminal. = himpunan terminal/ alfabet P = aturan produksi, yakni A dengan A N, (N )* S = simbol awal Ingat materi Teori Bahasa mengenai ciri CFG
- 8. Penurunan String (Derivation) Dalam suatu grammar G, suatu string yang mengandung simbol nonterminal ( 1) dapat menurunkan bentuk terminal ( Dituliskan dengan 1 * m). m. Seluruh sentence (ingat materi Teori Bahasa) dapat membentuk suatu bahasa, yang dinotasikan dengan L(G) L(G) = { w | w dalam *, dan S *w}
- 9. CFL (Context-Free Language) Seluruh sentence (ingat materi Teori Bahasa) dapat membentuk suatu bahasa, yang dinotasikan dengan L(G) L(G) = { w | w dalam *, dan S *w} Bahasa dari suatu grammar (G) adalah seluruh sentence yang terdiri dari alfabet dalam G, dan diturunkan dari simbol awal S
- 10. Contoh 3: Penurunan G = ({S}, {a,b}, P, S) Dengan P adalah: S aSb S ab Maka, Turunan yang dihasilkan: S aSb aabb S aSb aaSbb aaabbb S aSb aaSbb aaaSbbb jumlah a dan b sama aaaabbbb
- 11. Contoh 3 (lanjutan): Penurunan Turunan yang dihasilkan: S aSb aabb S aSb aaSbb aaabbb S aSb aaSbb aaaSbbb Dituliskan dalam bentuk L(G) L(G) = {anbn | n 1} jumlah a dan b sama aaaabbbb
- 12. Pohon Penurunan (Derivation Tree) root Penurunan dapat juga dinyatakan dalam bentuk tree/pohon. Sebagai root adalah simbol awal (S). no de no de
- 13. Pohon Penurunan (Derivation Tree) S Penurunan dapat juga dinyatakan dalam bentuk tree/pohon. Sebagai root adalah simbol awal (S). Node dapat berupa terminal atau nonterminal. no de no de
- 14. Pohon Penurunan (Derivation Tree) S Penurunan dapat juga dinyatakan dalam bentuk tree/pohon. A Sebagai root adalah simbol awal (S) Node dapat berupa terminal atau nonterminal. Setiap nonterminal harus diturunkan hingga membentuk terminal. a
- 15. Pohon Penurunan (Derivation Tree) S Penurunan dapat juga dinyatakan dalam bentuk tree/pohon. A Sebagai root adalah simbol awal (S) Node dapat berupa terminal atau nonterminal. Setiap nonterminal harus diturunkan hingga membentuk terminal. a a
- 16. Contoh 4: Latihan G = ({S, A}, {a,b}, P, S) P adalah: S aAS Sa A SbA A SS A ba Salah satu turunannya adalah aabbaa, buktikan dengan pohon penurunan!
- 17. Contoh 4 (lanjutan): Latihan Aturan Produksi: S aAS Sa A SbA A SS A ba String aabbaa diperoleh melalui: S a S a A S b A b a a
- 18. Contoh 4 (lanjutan): Latihan Aturan Produksi: S aAS Sa A SbA A SS A ba String aabbaa diperoleh melalui: S a S a A S b A b a a
- 19. Keambiguan Proses Penurunan ada 2 cara: 1. Dari sisi kiri (l e f t - m o s t ) : diturunkan satu-per-satu dari kiri. 2. Dari sisi kanan (r i g h t - m o s t ) : diturunkan satu-per-satu dari kanan. Jika suatu string diturunkan dari dua/lebih proses penurunan yang sama (keduanya left-most atau keduanya right-most) Maka keambiguan akan terjadi !
- 20. Contoh 5: Keambiguan CFG dengan aturan produksi: EE+E EE*E E (E) Ea String a + a * a merupakan string ambigu karena string tersebut memiliki dua proses penurunan left-most. Mari kita lihat buktinya!
- 21. Aturan Produksi: EE+E EE*E E (E) Ea Contoh 5 (lanjutan): Keambiguan Penurunan LeftMost E E a + E a beda E * E E E E a a + * E a E a
- 22. Aturan Produksi: EE+E EE*E E (E) Ea Contoh 5 (lanjutan): Keambiguan Penurunan LeftMost E E a + E a beda E * E E E E a a + * E E a a *Kedua pohon tersebut berbeda, namun menghasilkan string yang sama terbukti ambigu!
- 23. Palindrome String yang jika dibaca dari kiri ke kanan akan sama dengan jika dibaca dari kanan ke kiri Contoh Palindrome: OTTO DOOM MOOD STAR RATS STEP ON NO PETS WASITARATISAW (dibaca: Was it a rat I saw)
- 24. Info Tugas: Tugas kuliah ke-8 (khusus kelas B) : Tugas-1 Tugas kuliah ke-9 (kelas A dan kelas B) : Tugas-2 Jika ada permasalahan seputar tugas, silakan hubungi saya di ruangan (khususnya pada jam matakuliah Teori Bahasa & Otomata). Thanks!