Blog Teori Bahasa Dan Otomata tentang Derivasi Kalimat dan Penentuan Bahasa || Siti Nurul Maghfirah L_ 202131125

                                                                                             Institute Teknologi PLN Jakarta

                                                            Dosen : Dine Tiara Kusuma S.T., M.Kom

Derivasi Kalimat dan Penentuan Bahasa

Grammar

Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Aturan produksui merupkan pusat dari 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 (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 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}