Teknik - teknik penyederhanaan produksi

Latihan Penyederhanaan Tata Bahasa Bebas Konteks

A. Penyederhanaan dengan penghilangan produksi useless

       Soal Latihan :

      1. Penyederhanaan dengan penghilangan produksi Useless 

          S → aB | C

          B → e | Ab

          C → bCb | adF | ab

          F → cFB

      Analisa :

         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



    2. Penyederhanaan dengan penghilangan produksi Useless

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

      Analisa :
      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
     B → ab
     C → b

B. Penyederhanaan dengan penghilangan produksi unit
       Soal Latihan :

      1. Penyederhanaan dengan penghilangan produksi Unit
         S → Aa | B
         B→ A | bb
         A → a | bc | B


       Analisa :

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

      Hasil Penyederhanaan :
      S → Aa | a | bc | bb
      B → a | bc | bb
      A → a | bc | bb


    2. Penyederhanaan dengan penghilangan produksi Unit

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

       Analisa :

       C → D ==> C → b
       B → C ==> B → b | ab , Karena B → b sudah ada maka cukup ditulis 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

    

C. Penyederhanaan dengan penghilangan produksi empty (ε)
       Soal Latihan :
     1. Penyederhanaan dengan penghilangan produksi Empty (ε)
        S → AB
        A → abB | aCa | ε
        B → bA | BB | ε
        C → ε

      Analisa :
       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

  2. Penyederhanaan dengan penghilangan produksi Empty (ε)
      S → aBCD | bb | A | ε
      A → CDa | ef
      B → b | Af | ε
      C → BbC | ea
      D → ε

      Analisa :
      Variabel yang nullable: S,B,D, maka:
      S → ε (dihapus)
      B → ε (dihapus)
      D → ε (dihapus)

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

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

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


Untuk menjawab soal latihan kompleks diatas saya harus megerjakannya sesuai urutan penyederhanaan tata bahasa bebas konteks. Pertama menghilangkan produksi empty(ε), setelah itu menghilangkan produksi unit, dan terakhir menghilangkan produksi useless.
Jawab :


     Penghilangan produksi empty(ε) :

      Analisa:
        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 :
      Analisa:

       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:

      Analisa:

       D → d (D → d adalah redudan)

   Hasil Akhir Penyederhanaan :
     S → BACa |BAa | BCa
     B → AC | dC | d
     A → dC | d
     C → d

Video Pembahasan Penyederhanaan Tata Bahasa Bebas Konteks