Derivasi Kalimat dan Penentuan Bahasa

 

" Derivasi Kalimat & Penentuan Bahasa "

Grammar dan Bahasa

    Grammar adalah sebagai kumpulan himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, dibatasi oleh 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 " alpa -> beta " (bisa dibaca alpa menghasilkan beta, atau dibaca alpa menurunkan beta). Alpa merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan beta merupakan simbol-simbol ruas kanan aturan produksi. 

    Simbol-simbol tersebut dapat berupa imbol 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 sebuah string. Contoh aturan produksi :

E -> T | T+E | T*E

T -> a

Dari aturan produksi diatas, 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 (atau himpunan token-token, atau alfabet)

VN : himpunan simbol-simbol non terminal)

S : simcol awal (atau simbol start)

Q : himpunan produksi

Derivasi Kalimat dan Penentuan Bahasa

Tentukan bahasa dari masing-masing grammar berikut : 

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

Jawaban : 

Derivasi kalimat terpendek :

S    => aAa (1)

      => aba (3)

Derivasi kalimat umum :

S    => aAa (1)

      => aaAaa (2)

      => a^nAa^n (2)

      => a^nba^n (3)

Dari pola kedua kalimat disimpulkan :

L1(G1) = {a^nba^n | n >= 1}