Grammar & Bahasa

Materi 2

Grammar dan Bahasa

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 "a » B "  (bisa dibaca a menghasilkan B, atau dibaca a menurunkan B).
• a merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan B 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 lagt, 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 (G) didefinidikan sebagai pasangan 4 tuple yaitu VT, VN, S, dan Q. Ditulis sebagai G(Vт, Vɴ, S, Q), dimana :

Vт : himpunan simbol-simbol terminal (atau himpunan token-token, atau alfabet)

Vɴ : himpunan simbol-simbol non terminal

S : simbol awal (atau simbol start)

Q : himpunan produksi

Contoh:  

Tentukan bahasa dari masing-masing gramar berikut :

G, dengan Q, = (1.5 -> aAa,  2. A -> aAa,  3. A -> b).

Jawab: 

Derivasi kalimat terpendek : 

S ⇒ aAa (1) 
   ⇒ aba (3)  

Derivasi kalimat umum :

S ⇒ aAa (1) 
   ⇒ aba (3)
   ⇒ aaAaa(2)
 ⋯ 
   ⇒ aⁿAaⁿ (2)  
   ⇒ aⁿbaⁿ (3)  

Dari pola kedua kalimat disimpulkan :

L↿ (G↿) = ( aⁿbaⁿ | n ≥ 1)