Soal Quiz susulan

1)  S -> AA | b
      A -> SS | d
      Ubah dalam Bentuk GNF

2) S -> aSb  | ab
     Ubah dalam bentuk GNF
     Buat Pohon Penurunannya untuk mendapatkan string "aabb"
    dari bentuk aturan produksi yang berbentuk GNF

Jawaban UAS FOC3 2009-2010 genap

Jawaban UAS FOC3 2009/2010 Genap sore Klik disini

Jawaban Tugas FOC3 Sore 2009/2010 genap

Jawaban Tugas FOC3 sore 2009/2010 sore (CFG,CYK) Klik disini

SOAL UAS OOP Elektro Sore SMT Ganjil 2009

Soal Uas Teknik Elektro Paruh Waktu dapat di lihat disini

Pembahasan Tugas FOC 3 seri 1

pembahasan mengenai e-move -> NDFA -> DFA baca dan download di sini

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

PENYEDERHANAAN
TATA BAHASA BEBAS KONTEKS

Cara Penyederhanaan:
1. Penghilangan produksi useless ( tidak berguna )
2. Penghilangan produksi unit
3. Penghilangan produksi e



Penghilangan Produksi Useless

Di sini produksi useless didefinisikan sebagai :
- Produksi yang memuat symbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya.
- Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan ( berlebih )

Contoh :
S → aSa | Abd | Bde
A → Ada
B → BBB | a
Maka
1) Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa
dihilangkan
2) Konsekuensi no (1), aturan produksi S → Abd tidak memiliki penurunan

Penyederhanaan menjadi:
S → aSa | Bde
B → BBB | a

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

Maka :
1) Aturan produksi A → D, simbol variabel D tidak memiliki penurunan.
2) Aturan produksi C → bb, Penurunan dari simbol S, dengan jalan manapun tidak
akan pernah mencapai C
3) Simbol variabel E tidak memiliki aturan produksi yang menuju terminal
4) Konsekuensi no (3) Aturan produksi B → E, simbol variabel E tidak memiliki
penurunan.
maka produksi yang useless:
A → D
C → bb
E → aEa
B → E
Penyederhanaannya menjadi:
S → Aa | B
A → ab
B → b

Penghilangan Produksi Unit
Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel,
misalkan: A → B, C → D.
Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.
Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.

Contoh:
S → Sb
S → C
C → D
C → ef
D → dd

Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju
ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’):
C → D => C → dd S → C => S → dd | ef
Sehingga aturan produksi setelah penyederhanaan:
S → Sb
S → dd | ef
C → dd
C → ef
C → dd

Penghilangan Produksi ε
Produksi ε adalah produksi dalam bentuk
a → ε

atau bisa dianggap sebagai produksi kosong ( empty ). Penghilangan produksi e
dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa
menuju produksi e, atau biasa disebut nullable.
Prinsip penggantiannya bisa dilihat kasus berikut:
S → bcAd
A → ε
A nullable serta A → ε satu-satunya produksi dari A, maka variabel A bisa
ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi:

S → bcd


Tetapi bila kasusnya:

S → bcAd
A → bd | ε

A nullable, tapi A → e bukan satu-satunya produksi dari A, maka hasil
penyederhanaan:

S → bcAd | bcd
A → bd


Contoh :

S → Ab | Cd
A → d
C → ε

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

Setelah penyederhanaan menjadi:

S → Ab | d
A → d

Prakteknya ketiga penyederhanaan tersebut dilakukan bersama pada suatu tata bahasa bebas konteks.

lihat Persentasi
Latihan
Hilangkan ε -production di bawah ini
1. S → ABaC
2. A → BC
3. B → b | ε
4. C → D | ε
5. D → d

Materi Fundamental of Computer3

Pembahasan Quiz FOC3 Cohomsky method Download disini

Materi AI Sistem pakar-ketidakpastian,fuzzy, JST

Materi AI Fuzzy dan Jaringan Syaraf Tiruan silahkan download di sini

REGUDUKAN