Grammar Dan Bahasa || Nur Anisah Fadhilah - 202131020

Institut Teknologi PLN Jakarta

Dosen : DINE TIARA KUSUMA, S.T., M.Kom

GRAMMAR DAN BAHASA

Grammar

Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Aturan Produksi merupakan pusat grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya.

Semua aturan produksi dinyatakan dalam bentuk "ɑ => β" (bisa dibaca ɑ menghasilkan β, atau dibaca ɑ menurunkan β). ɑ merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbol-simbol ruas kanan aturan produksi.

• Simbol-simbol tersebut dapat berupa Simbol Terminal (Vt) atau Simbol Non-Terminal/Variabel (Vn).
• Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar/kapital 'A', 'B', 'C'.
• Simbol Vt adalah simbol yang sudah tidak dapat diturunkan, biasanya identik dengan huruf kecil 'a', 'b', 'c'.

Dengan menerapkan aturan produksi, suatu grammar bisa menghasilkan sejumlah string.

Contoh aturan produksi :

1. E => T | T + E | T * E
2. T => a

Dari aturan produksi diatas, menghasilkan suatu variabel a atau variabel ekspresi a+a atau a*a.

1. E => T

    T => a

2. E => T + E

    E => a + T

    E => a + a

3. E => T * E

    E => a * T

    E => a * a

Grammar (G) di definisikan sebagai pasangan 4 tupple : Vt, Vn, S, dan Q. Dapat dituliskan sebagai G(Vt, Vn, S, dan Q) dimana :

Vt : Himpunan simbol-simbol terminal (himpunan token-token atau alfabet).

Vn : Himpunan simbol-simbol non terminal.

S : Simbol awal (simbol start).

Q : Himpunan produksi.

Derivarasi Kalimat Dan Penentuan Bahasa

1. Tentukan bahasa dari masing-masing grammar berikut : 

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

    Jawab :  

    - Derivasi Kalimat Terpendek : 

       S => aAa     (1)

       S => aba      (3)

    - Derivasi Kalimat Umum : 

       S => aAa           (1)

       S => aaAaa       (3)

       S => aaaAaaa    (1)

       S => aaabaaa     (3)

    - Dari pola kedua kalimat disimpulkan : 

       L₁(G₁) = {aⁿbaⁿ | n >= 1}

 2. Tentukan bahasa dari masing-masing grammar berikut : 

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

    Jawab :  

    - Derivasi Kalimat Terpendek 1 :

       S => aS           (1)

       S => aaB         (2)

       S => aabC       (3)

       S => aaba        (5)

    - Derivasi Kalimat Terpendek 1 :

       S => aS           (1)

       S => aaB         (2)

       S => aabC       (3)

       S => aabaC     (4)

       S => aabaa      (5)

    - Derivasi Kalimat Umum : 

       S => aS               (1)

       S => aaS             (1)

       S => aaaS           (1)

       S => aaaaB         (2)

       S => aaaabC       (3)

       S => aaaabaC     (4)

       S => aaaabaaC   (4)

       S => aaaabaaa    (5)

    - Dari pola kedua kalimat disimpulkan : 

      L₂(G₂) = {aⁿba^m | n > 1, m >= 1}