TEORI BAHASA DAN AUTOMATA

-

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Tujuan Penyederhanaan :
  • Untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tidak berarti.
Misal :
  • Diketahui suatu tata bahasa bebas konteks : 
          S → AB | a
          A → a
  • Kelemahan : 
          Aturan produksi  S → AB tidak berarti karena B tidak memiliki penurunan

Tata Bahasa Bebas Konteks dapat disederhanakan dengan melakukan cara berikut :
  1. Penghilangan Produksi Useless
  2. Penghilangan Produksi Unit
  3. Penghilangan Produksi Empty ℇ/epsilon


1. Penghilangan Produksi Useless

Produksi Useless adalah aturan produksi yang tidak menghasilkan terminal-terminal simbol atau aturan produksi yang tidak pernah terjangkau dan tercapai dengan penurunan apapun dari simbol awal sehingga Redudan(berlebih)
    
Contoh soal 1 :
S → AB | C
B → e | Ab
C → bCb | adF | ab
F → cFB

Cara Penyeselaian :
➤ F pada F ⟶ eFB tidak memiliki penurunan ke terminal
➤ A pada B ⟶ Ab tidak memiliki penurunan 
➤ F pada C ⟶ adF tidak memiliki penurunan

Jadi hasilnya adalah :
S ⟶ AB | C
B →  e
C → beb | ab

Contoh soal 2 :
S → Aa | B  
A → ab | D  
B → b | E 
C → bb
E → aEa

Cara Penyelesaian :
➤ D pada A → D tidak memiliki penurunan
➤ C → bb (Redudan)
➤ E pada B → E tidak memiliki penurunan

Jadi hasilnya adalah :
S → Aa | B
A → ab
B → b

2. Penghilangan Produksi Unit 

Produksi yang dimana ruas kiri dan kanan aturan produksi hanya berupa 1 buah simbol variabel.
A → B
B → C
C → D

Contoh soal 1 :
S → Aa | B
B → A | bb
A → a | bc | B

Cara Penyelesaian :
➤ S → Aa
➤ S → B a | bc | bb
➤ B → A a | bc | bb
➤ B → bb
➤ A → a
➤ A → bc
➤ A → B bb

Jadi hasilnya adalah :
S → Aa
B → a
A → a

Contoh soal 2 :
S → A | Aa
A → B
B → C | b
C → D | ab
D → b

Cara Penyelesaian :
➤ C → D | ab, D diganti jadi b
➤ B → C | b, C diganti ab | b
➤ A → B, B diganti jadi ab | b
➤ S → A | Aa, A diganti jadi ab | b

Jadi hasilnya adalah :
S → ab | b | Aa
A → ab | b
B → ab | b
C → b | ab
D → b

3. Penghilangan Produksi Empty (𝜺)

Aturan produksi dalam bentuk 𝜶 → 𝜺
Penghilangan produksi 𝜺 dilakukan dengan melakukan pergantian produksi yang memuat variabel yang bisa menuju 𝜺 atau biasa disebut juga nullable.

Contoh soal 1 :
S → AB
A → abB | aCa | 𝜺
B → bA | BB | 𝜺
C → 𝜺

Cara Penyelesaian :
1) Hilangkan 𝜺 pada C
S → AB
A → abB | aa | 𝜺
B → bA | BB | 𝜺

2) Hilangkan 𝜺 pada B
S → AB | A
A → abB | aa | 𝜺 | ab
B → bA | BB

3) Hilangkan 𝜺 pada A
S → AB | B
A → abB | aa | ab
B → bA | BB | b

Jadi hasilnya adalah :
S → AB | B
A → abB | aa | ab
B → bA | BB | b

Contoh soal 2 :
S → aBCD | bb | A | 𝜺
A → CDa | ef
B → b | Af | 𝜺
C → BbC | ea
D → 𝜺

Cara Penyelesaian :
1) Hilangkan 𝜺 pada D
S → aBC | bb | A | 𝜺
A → Ca | ef 
B → b | Af | 𝜺
C → BbC | ea

2) Hilangkan 𝜺 pada B
S → aBC | bb | A | 𝜺 | aC
A → Ca | ef
B → b | Af
C → BbC | ea | bC

3) Hilangkan 𝜺 pada S
S → aBC | bb | A | aC
A → Ca | ef 
B → b | Af
C → BbC | ea | bC

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

4. Penyederhanaan Kompleks

Penghilangan  produksi useless, produksi unit dan produksi empty sekaligus.

Contoh soal 1 :
S → BACa
B → AC
A → dC | 𝜺
C → D | 𝜺
D → d

Cara Penyelesaian :
1) Hilangkan produksi empty
Hilangkan 𝜺 pada C
S → BACa | Baa
B → AC | A
A → dC | 𝜺 | d
C → D
D → d
Hilangkan 𝜺 pada A 
S → BACa | BAa | BCa
B → AC | A | C | 𝜺
A → dC | d
C → D
D → d
Hilangkan 𝜺 pada B
S → BACa | BAa | BCa | Ba | ACa | Aa | Ca | a
B → AC | A | C
A → dC | d
C → D
D → d

2) Penghilangan produksi unit
C → D, D diganti jadi d
B → C, C diganti jadi d
B → A, A diganti jadi dC | d

Jadi hasilnya adalah :
S → BACa | BAa | BCa | Ba | ACa | Aa | Ca | a
B → AC | dC | d
A → dC | d
C → d
D → d

3) Karena pada produksi tidak ada yang memenuhi syarat aturan produksi useless, maka tidak perlu diadakan penghilangan produksi useless dan langkah selesai. Jadi untuk hasil akhir dari penyederhanaan kompleks ini adalah hasil dari penyederhanaan pada langkah penghilangan produksi unit, yaitu :

S → BACa | BAa | BCa | Ba | ACa | Aa | Ca | a
B → AC | dC | d
A → dC | d
C → d
D → d

Dibawah ini merupakan video penjelasan dari penyederhanaan tata bahasa bebas konteks :

Daftar Pustaka :
- Materi 5 Perkuliahan "Tata Bahasa Bebas Konteks (Penyederhanaan)" Dosen pengampu Teori Bahasa dan Automata : Garno, M,Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang



Terimakasih, semoga dapat bermanfaat. Mohon maaf apabila ada kesalahan kata dalam penulisan, jika ada kesalahan silahkan tulis di kolom komentar.

Komentar

Posting Komentar

Postingan populer dari blog ini

TEORI BAHASA DAN AUTOMATA

-
Gambar
Tata Bahasa Bebas Konteks (POHON PENURUNAN) Hirarky Chomsky Tata Bahasa Bebas Konteks (Context Free Grammar/CFG) Adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa. Menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis, bagian sintaksis dalam suatu kompilator kebanyakan didefinisikan dalam tata bahasa bebaas konteks. Terbagi menjadi 2 yaitu PARSING dan AMBIGUITAS 1. PARSING Pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) yang disebut akar (root) dan dari situ memiliki lintasan ke setiap simpul. Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurukan simbol-simbol variabel menjadi simbol-simbol terminal. Latihan 1 S → AB A → AAA | a | bA | Ab Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan "bbabaaba" . Jawab : Baca ...
Baca selengkapnya

TEORI BAHASA DAN AUTOMATA

-
Gambar
Finite State Automata Materi yang akan kita bahasa adalah : 1. Penerapan FSA (Finite State Automata) 2. Penerapan DFA (Deterministic Finite Automata) 3. Penerapan NFA (Nonfeterministic Finite Automata) 4. Ekuivalen antar DFA 5. Reduksi Jumlah State Pembahasannya : 1. Penerapan FSA (Finite State Automata) Finite State Automata atau automata berhingga state, selanjutnya disebut sebagai FSA yaitu suatu model matematika dari suatu sistem yang menerima input dan ouput diskrit. FSA merupakan mesin automta dari bahas regular, suatu FSA memiliki state yang banyaknya berhingga dan dapat berpindah-pindah dari suatu state ke state lain. Perubahan state ini dinyatakan oleh fungsi transisi. FSA tidak memiliki tempat penyimpanan, sehingga kemampuan 'mengingatnya' terbatas, hanya bisa mengingat state yang terkini. Contoh FSA antara lain elevator, text editor, analisa leksikal, protocol komunikasi jaringan dan pencek parity. FSA berdasar pada pendefinisian kemampuan ...
Baca selengkapnya