Teori Bahasa Dan Automata - Tata Bahasa Bebas Konteks (Latihan Penyederhanaan)

Dibuat Oleh pada
Assalamualaikum Wr. Wb.

Pada postingan ini saya akan membagikan sebuah materi penyederhanaan tata bahasa bebas konteks. Tujuan saya membuat postingan ini adalah untuk memenuhi Tugas Materi 5 pada Mata Perkuliahan TEORI BAHASA DAN AUTOMATA.


Disini saya akan membahas latihan dari penyederhanaan tata bahasa bebas konteks baik dengan menggunakan cara penghilangan produksi useless, penghilangan produksi unit, maupun penghilangan produksi empty(ε).

1. Penyederhanaan dengan penghilangan produksi Useless

Untuk menjawab soal latihan penyederhanaan dengan penghilangan produksi useless kita harus menghapus aturan produksi yang tidak memiliki penurunan dan juga aturan produksi yang berlebih atau redudan.

    Soal Latihan 1
    Penyederhanaan dengan penghilangan Produksi Useless
       S → aB | C
       B → e | Ab
       C → bCb | adF | ab
       F → cFB

    Proses Penyederhanaan:
       1.         S → aB
       2.         S → C
       3.         B → e
       4.         B → Ab            (A tidak punya penurunan)
       5.         C → bCb
       6.         C → adF          (F tidak punya penurunan)
       7.         C → ab
       8.         F → cFB           (F tidak punya penurunan ke terminal)

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

    Soal Latihan 2
    Penyederhanaan dengan penghilangan Produksi Useless
        S → Aa | B
        A → ab | D
        B → b | E
        C → bb
        E → aEa

    Proses Penyederhanaan:
       1.         S → Aa
       2.         S → B
       3.         A → ab
       4.         A → D              (D tidak punya penurunan)
       5.         B → b
       6.         B → E              (Konsekuensi proses ke-8)
       7.         C → bb            (Redundan)
       8.         E → aEa          (E tidak punya penurunan ke terminal)

    Hasil:
       S → Aa | B
       B → ab
       B → b

2. Penyederhanaan dengan penghilangan Produksi Unit

Untuk menjawab soal latihan penyederhanan dengan penghilangan produksi unit (produksi di mana ruas kiri dan kanan hanya terdapat satu simbol variabel) yaitu dengan cara penggantian produksi unit berurutan mulai dari aturan produksi yang paling dekat ke terminal.

    Soal Latihan 1
    Penyederhanaan dengan menghilangkan Produksi Unit
       S → Aa | B
       B→ A | bb
       A → a | bc | B

   Proses Pergantian (Penghilangan Produksi unit):
      1.         S → Aa
      2.         S → B              (diganti menjadi S → a | bb | bc)
      3.         B → A              (diganti menjadi B → a | bc)
      4.         B → bb
      5.         A → a
      6.         A → bc
      7.         A → B              (diganti menjadi A → bb)

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

    Soal Latihan 2
    Penyederhanaan dengan menghilangkan Produksi Unit
       S → A | Aa
       A→ B
       B → C | b
       C → D | ab
       D → b

   Proses Penggantian (Penghilangan Produksi Unit):
      1.         S → A              (diganti menjadi S → b)
      2.         S → Aa
      3.         A → B              (diganti menjadi A → b | ab)
      4.         B → C              (diganti menjadi B → ab | b)
      5.         B → b
      6.         C → D              (diganti menjadi C → b)
      7.         C → ab           
      8.         D → b

   Hasil Penyederhanaan:
      S → b | Aa
      A → b | ab
      B → ab | b
      C → b | ab
      D → b

3. Penyederhanaan dengan penghilangan Produksi Empty (ε)

Untuk menjawab soal latihan penyederhanaan dengan penghilangan Produksi Empty yaitu dengan cara melakukan penggantian produksi yang nullable.

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

   Proses Penyederhanaan:
      1.         S → AB            (diganti menjadi S → AB | A | B)
      2.         A → abB          (diganti menjadi A → abB | ab)
      3.         A → aCa          (diganti menjadi A → aa)
      4.         A → ε              (nullable, dihapus)
      5.         B → bA            (diganti menjadi B → bA | b)
      6.         B → BB            (diganti menjadi B → BB | B)
      7.         B → ε              (nullable, dihapus)
      8.         C → ε              (nullable, dihapus)

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

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

   Proses Penyederhanaan:
      1.         S → aBCD        (diganti menjadi S → aBCD | aBC | aBD | aCD | aa )
      2.         S → bb
      3.         S → A
      4.         S → ε              (nullable, dihapus)
      5.         A → cDa          (diganti menjadi A → Ca | Da )
      6.         A → ef
      7.         B → b
      8.         B → Af            (diganti menjadi B → Af | f )
      9.         B → ε              (nullable, dihapus)
      10.       C → BbC          (diganti menjadi C → bc)
      11.       C → ea           
      12.       D → ε              (nullable, dihapus)

   Hasil:
      S → aBCD | aBC | aBD | aCD | aa | bb | A
      A → Ca | Da | ef
      B → b | Af | f
      C → 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

   Proses Penyederhanaan:
      1.         S → BACa        (konsekuensi proses ke 2, 3, 4, 5, 6)
      2.         B → AC            (konsekuensi proses ke-3, 4, 5, 6)
      3.         A → dC            (C tidak punya turunan)
      4.         A → ε              (nullable, dihapus)
      5.         C → D              (konsekuensi proses ke-7)
      6.         C → ε              (nullable, dihapus)
      7.         D → d              (redundant)

   Hasil:
      S → ε


Video Penjelasan:

 Video juga bisa ditonton Youtube

Itulah hasil penjelasan saya, mohon maaf apabila terdapat kesalahan dalam proses pengerjaan. Semoga ilmu yang ada di postingan saya dapat bermanfaat bagi kita semua.

Terima Kasih

Wassalamualaikum Wr. Wb.
-----------------------------------------------------------------------------------------------------------------------------------------------
Daftar Pustaka:
Materi Persentasi "Penyederhaan Tata Bahasa Bebas Konteks" Dosen pengampu Teori Bahasa Automata: Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang
https://herilovemetallica.blogspot.com/2009/10/penyederhanaan-tata-bahasa-dalam-teori.html
https://slideplayer.info/slide/3649861/

Komentar

Posting Komentar