Tugas 5 Teori Bahasa dan Automata - Penyederhanaan Tata Bahasa Bebas Konteks

Luky Mulana (1810631170200) 4G - Tujuan penyederhanaan adalah untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.

      3.   Penghilangkan Produksi Empty

Setiap teknik mempunyai caranya masing-masing, bagaimana caranya. Mari kita bahas satu persatu.

1. Penghilangan Produksi Useless

Produksi Useless adalah produksi yang memuat simbol variable yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya dan produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produk itu redudan.
Contoh:

Terdapat aturan produksi sebagai berikut :

            S → aBD

            B → cD | Ab

            D → ef

            A → Ed

            F → dc

Penggunaan Produk Useless :

1. Aturan produksi A → Ed , E tidak memiliki penurunan. Sehingga dapat dihilangkan.
2. Aturan produksi F → dc, redudan. Sehingga aturan produksi tersebut dapat dihilangkan.
3. Aturan produksi B → Ab, A tidak memiliki penurunan. Sehingga dapat dihilangkan.

Maka hasil akhirnya:

            S → aBD

            B → cD

            D → ef


2. Penghilangan Produksi Unit

Produksi Unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel. Contoh A → B, atau C → D.

Contoh :

Diberikan aturan produksi sebagai berikut :

            S → Sb

            S → C

            C → D

            C → ef

            D → dd

Penggunaan Produk Useless :

            C  → D => C → dd

            S → C => S → dd | ef

Sehingga aturan produksi yang telah disederhanakan dengan menghilangkan produksi unit adalah sebagai berikut :

           S → Sb

           S → dd | ef

           C → dd

           C → ef

           D → dd

3. Penghilangan Produksi Empty (ε)

Produksi Empty adalah produksi dalam bentuk α → ε atau bisa dianggap sebagai produksi kosong (empty). Penghilangan produksi  empty dilakukan dengan melakukan penggantian produksi yang memuat variable ε, atau disebut juga Nullable.

Contoh :

Terdapat tata bahasa bebas konteks sebagai berikut :

            S → aB | Cd

            A → d

            C → ε

Variabel yang nullable adalah variable C, karena penurunan C → ε merupakan penurunan satu-satunya dari C, maka kita ganti S → Cd menjadi S → d, kemudian produksi C → ε kita hapus.

Maka hasil penyederhanaannya adalah :

            S → aB | d

            A → d

Alur Penyederhanaan Tata Bahasa Bebas Konteks



Selanjutnya ada pembahasan mengenai soal latihan penyederhanaan tata bahasa bebas konteks. Dalam soal latihan tersebut akan dijabarkan pengerjaan dalam setiap teknik yang diguanakan dalam penyerderhanaan tata bahasa bebas konteks.

Soal Latihan 

1. Penyederhanaan dengan penghilangan produksi useless

    a. Soal Latihan 1

        S → aB | C
        B → e | Ab
        C → bCb | adF | ab
        F → cFB
    
        Jawab :

        Penghilangan Produksi Useless:

            B → Ab (A tidak punya penurunan)
            C → adF (F tidak punya penurunan)
            F → cFB (F tidak punya penurunan ke terminal)

        Hasil Penyederhanaan:

            S → aB | C
            B → e
            C → bCb | ab

     
    b. Soal Latihan 2

        S → Aa | B
        A → ab | D
        B → b | E
        C → bb
        E → aEa 

        Jawab :

        Penghilangan Produksi Useless:

             A → D (A tidak punya penurunan)
             B → E (F tidak punya penurunan)
             C → bb (C → bb adalah redudan)
             E → aEa (E tidak punya penurunan ke terminal)

        Hasil Penyederhanaan: 

             S → Aa | B
             A → ab
             B → b

2. Penyederhanaan dengan penghilangan produksi unit

    a. Soal Latihan 1

        S → Aa | B
        B → A | bb
        A → a | bc | B

        Jawab :

        Penghilangan produksi unit:

             A → B  ==>  A → bb 
             B → A  ==>  B → a | bc | bb , Karena B → bb sudah ada maka cukup B → a | bc
             S → B  ==>   S → a | bc | bb

      Hasil Penyederhanaan:

             S → Aa | a | bc | bb
             B → a | bc | bb
             A → a | bc | bb

   
    b. Soal Latihan 2

         S → A | Aa
         A→ B
         B → C | b
         C → D | ab
         D → b

         Jawab :

         Penghilangan produksi unit:

              C → D  ==>  C → b
              B → C  ==>  B → b | ab , Karena B → b sudah ada maka cukup B → ab
              A → B  ==>   A → ab | b 
              S → A  ==>   S → ab | b

         Hasil Penyederhanaan:

              S → ab | b | Aa
              A → ab | b
              B → ab | b
              C → b | ab
              D → b


3. Penyederhanaan dengan penghilangan produksi empty (ε)

    a. Soal Latihan 1

        S → AB
        A → abB | aCa | ε
        B → bA | BB | ε
        C → ε

        Jawab :        
        Penghilangan produksi empty(ε):

        Variabel yang nullable: A,B,C, maka:

            A → ε (dihapus) 
            Maka, S → AB | B
                       A → abB | ab | aa
                       B → b | BB 

             B → ε (dihapus)
             Maka, S → AB | A
                        B → bA  | BB | B
                        A → abB | ab | aa

             C → ε (dihapus)
             Maka, A → abB | aa

       Hasil Penyederhanaan:

              S → AB | A | B
              A → abB | ab | aa
              B → bA | b | BB | B

   
   b. Soal Latihan 2

        S → aBCD | bb | A | ε
        A → CDa | ef
        B → b | Af | ε
        C → BbC | ea
        D → ε

        Jawab :

        Penghilangan produksi empty(ε):
           
        Variabel yang nullable: S,B,D, maka:

              D → ε (dihapus)
              Maka, A → CDa | ef  ==>  A → Ca | ef
                         S → aBCD | bb | A | ε  ==>  S → aBC | bb | A | ε 

              B → ε (dihapus)
              Maka, C → BbC | ea  ==>  C → BbC | bC| ea
                         S → aBC | bb | A | ε  ==>  S → aBC | aC | bb | A | ε

              S → ε (dihapus)
              Maka, S → aBC | aC | bb | A

       Hasil Penyederhanaan:

              S → aBC | aC | bb | A
              A → Ca | ef
              B → b | Af
              C → BbC | bC | ea

4. Latihan Kompleks
    
Lakukan penyederhanaan pada himpunan produksi berikut dengan penghilangan empty + unit + useless sekaligus.

        S → BACa
        B → AC
        A → dC | ε
        C → D | ε
        D → d

        Jawab :

        •   Penghilangan produksi empty(ε):

            Variabel yang nullable: A,C, maka:

                  A → ε (dihapus)
                  C → ε (dihapus)

             Maka:

                  S → BACa |BAa | BCa
                  B → AC | A | C
                  A → dC | d
                  C → D
                  D → d


        • Penghilangan produksi unit:

                  C → D  ==> C → d
                  B → A  ==> B → dC | d
                  B → C  ==> B → d

              Maka:

                   S → BACa |BAa | BCa
                   B → AC | dC | d
                   A → dC | d
                   C → d 
                   D → d

         • Penghilangan produksi useless:

                   D → d (D → d adalah redudan)

         • Hasil Akhir Penyederhanaan: 

                    S → BACa |BAa | BCa
                    B → AC | dC | d
                    A → dC | d
                    C → d

Untuk lebih jelasnya, saya menguraikan penjelasan soal latihan diatas menjadi video.