Materi 3

Derivasi Kalimat Dan Penentuan Bahasa

Derivasi

• Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : ɑ→β. 
• Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.
• Kalimat adalah string yang tersusun atas simbol-simbol terminal,, sehingga kalimat merupakan kasus khusus dari sentensial.
• Terminal berasal dari kata terminate (berakhir), maksudnya derivasi berakhir jika sentensial yang dihasilkan adalah sebuah kalimat (yang tersusun atas simbol-simbol terminal itu). umumya simbol terminal disimbolkan dengan huruf kecil.
• Non terminal berasal dari kata not terminate (belum/tidak berakhir), maksudnya derivasi belum/tidak berakhir jika sentensial yang dihasilkan mengandung simbol non terminal. umumnya simbol non terminal disimbolkan dengan huruf besar.

Grammar

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 
• VN : himpunan simbol-simbol non terminal
• S    : simbol awal (simbol start)
• Q   : himpunan produksi

Contoh soal, Tentukan bahasa dari masing-masing gramar berikut : 

1. G1 dengan Q1 = {1.S→aAa, 2.A→aAa, 3.A→b}

jawab :

Derivasi kalimat terpendek :                    

S→aAa        (1)

   →aba        (2)

Derivasi kalimat umum :

S → aAa         (1)

  →aaAaa       (2)

      …

  →anAan(2)

  → anban           (3)

Dari pola kedua kalimat dapat disimpulkan : L1(G1)={ anban|n>1}n ≥1}

2. G2 dengan Q2 = {1. S→aS, 2. S→A=aB, 3. B→bC, 4. C→aC, 5. C→a}

jawab :

Derivasi kalimat terpendek :

S→aB          (2)

   →abC       (3)

   →aba       (5)

Derivasi kalimat umum :

S→aS         (1)

   →aaS       (1)

   →aaaB     (2)

   →aaabC   (3)

   →aaabaC (4)

   →aaabaa  (5)

   →anbam

Dari pola kedua kalimat dapat disimpulkan : L1(G2)={anbam|n≥1,m ≥1}